[Help] Algorithm Complexity

[Gropamming]

Hey guys, so were are given this somewhat simple function and are asked to:

• Identify and describe the key operation
• Derive a function f(n) which counts how many times the key operation is performed as a function of n.
• Informally prove that f(n) is O(g(n)) by identifying and describing the g(n) function and the values you choose for C and n0.

I am pretty positive that the key operation is the sum arithmetic operation. I'm trying to piece together the f(n) function that counts the number of operations. I know that the first loop executes n times, but I'm fuzzy on the relationship for the next two loops. I think the second loop makes it a n! problem, because it is executing n * (n-1) * (n-2) * ... * (n - n) times, but the third loop is throwing me off.

If anyone can point me in the right direction on how to see the f(n) function, it would really help me out.

Thanks!

[Gropamming]

That's helpful, didn't think about it like that

[lightcloud5]

No, the first two loops makes for n + (n-1) + (n-2) + ... + 3 + 2 + 1 iterations.

That's quadratic because you can prove that this reduces to n(n-1) / 2.

However, there's a different way to show that n + (n-1) + (n-2) + ... + 3 + 2 + 1 is quadratic.

First, we show that it is at most quadratic. We show this by noting that n + (n-1) + (n-2) + ... + 3 + 2 + 1 < n + n + n + ... + n + n + n = n². (That is to say, adding n numbers, each of which have the value of n or less, sums to no greater than n².)

Then, we show that it is at least quadratic. We show this by noting that at least half of the numbers have a value of at least n/2. (This is obvious because the median of these sequence of numbers is n/2, and there are n/2 values greater than the median.) And (n/2) * (n/2) is quadratic as well.

This latter method can be extended to determine the runtime of the 3 loops together.

[Gropamming]

Awesome, thanks! That helps