Determine Big-O runtime for these loops

Question

I am trying to determine the Big-O runtimes for these loops. I believe the answers I have are correct, but I would like to check with the community.

int sum = 0;
for (int i = 1; i <= n*2; i++ )
   sum++;

My answer is O(n)

This is because the loop iterates n x 2 times. We drop the 2 and are left with n. Therefore O(n).

int sum = 0;
for ( int i = 1; i <= n; i++)
   for ( int j = n; j > 0; j /= 2)
      sum++;

My answer is O(n lgn)

The outer loop iterates n times. The inner loop iterates from n down to 0, but only through half of the items. This works out to be Log base 2 of n. We drop the 2 and keep log n. The inner loop (log n) times the outer loop (n), gives us O(n lgn).

int sum = 0;
for ( int i = 1; i <= n; i++)
   for ( int j = i; j <= n; j += 2)
      sum++;

My answer is O(n^2)

This one is easy. The inner loop and outer loop each iterate n times. n x n = n^2. Therefore O(n^2).

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

My answer is O(n^3)

Are my answers correct? If not, how can I correct them?

Can you explain how you arrived at your answers, especially the last one? — Scott Hunter, Nov 07 '15 at 02:29
@ScottHunter, all my work is written out in pen and paper, but I will try to update the question to include this. — Omar N, Nov 07 '15 at 02:37

William · Accepted Answer · 2015-11-07T02:48:01.380

2

Only the last one is wrong. It should be O(n⁴).

You can see it this way: substitute n * n with x. The number of operations will be the usual O(x*(x+1)/2) = O(x²). Now substitute n * n back into x.

Extra challenge for you.

You correctly said that:

int sum = 0;
for ( int i = 1; i <= n; i++)
   for ( int j = n; j > 0; j /= 2)
      sum++;

Is O(n log n). But what about this one:

int sum = 0;
for ( int i = 1; i <= n; i++)
   for ( int j = i; j > 0; j /= 2)
      sum++;

I only changed j = n to j = i.

edited Nov 07 '15 at 02:48

answered Nov 07 '15 at 02:41

William

2,695
1
21
33

1

If you give up, the answer is: it's the sum of O(log(i)) for i=1 to n, thus: O(log(1)+log(2)+log(3)+...+log(n)) = O(log(1*2*3*...*n)) = O(log(n!)) [= O(n log n)](http://stackoverflow.com/questions/8118221/what-is-ologn-and-on-and-stirling-approximation). – William Nov 07 '15 at 02:54
Thank you! This helped me a lot. I see where I went wrong on the last one. I guess another way to think about it is inner loop iterates 1+2+3+...+((n(n+1)/2)) times, which equals n^2. The outer loop also iterates n^2 times. So when multiplied, you get n^4 times. – Omar N Nov 07 '15 at 03:00

Determine Big-O runtime for these loops

1 Answers1