CODEWITHSUNDEEP
algorithmbig-o
User
User

Reputation: 1726

Determine Big-O runtime for these loops

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?

Upvotes: 2

Views: 2353

Answers (1)

William
William

Reputation: 2935

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.

Upvotes: 2

Related Questions