big-O alorithm efficiency?

Question

can someone help me to answer this question:

Express the tightest upper bound of the following loops in big-O notation.

a.

int sum = 0;
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
sum += j * k;


b.

for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
for (int l = 0; l < n; l++)
sum += j * k * l;


I just learned about big-O but I don't really know how to solve this. Can anyone please help me so I would understand more. Thanks

Answer 1

So I'm assuming you want O(n) where the costly operation is "sum += ;".

In (a), looking at the size of the loops, you basically have this:

do n times:
do n times:
expensive operation

Which means you'll do the expensive operation n*n (or n^2) times. Then you just write O(n^2)...

Based on that, I'm sure you can get (b).

Answer 2

a. is O(n^2) b. is in O(n^3), Big-O is a representation of how the algorithm slows down in sort of ratio proportion for n is increasing in size.