0

I've been struggling with my Analysis of Algorithms and Data Structures homework. With COVID-19 and e-learning, it has been difficult! Especially since my textbook was put on back order :(. I was wondering if any kind soul could help me with analyzing these O(n) problems.

I largely understand it, but I struggle greatly with counting primitive operations on loops, such as for( i = 0; i < 2n; i++ ).

Anyways, I will put them below. I will put my educated guesses below, btw. The biggest part for me is just understanding the primitive operations. Even if I got the right complexity, I still struggled to mathematically arrive at that solution. Thank you so much in advanced!

// #1 O(n)
sum = 0;
for( i = 0; i < 2n; i++ )
      sum++;

// #2 O(n^2)
sum = 0;
for( i = 0; i < 2n; i++ )
    for( j = 0; j < i; j++ )
         sum++;

// #3 O(n^4)
sum = 0;
for( i = 0; i < n2; i++)
    for( j = 0; j <  i; j++)
          sum++;

// #4 O(n^5)
sum = 0;
for( i = 0; i < n; i++)
   for( j = 0; j <  i*i; j++)
      for( k = 0; k <  j; k++)
          sum++;

3 Answers3

1

To put it simply, Time complexity refers how much time will our code take as we change the inputs, and is measured in terms of n(input size).

// #1 O(n)
sum = 0;
for( i = 0; i < 2n; i++ )
      sum++;

Time complexity for this is O(n), as you are just running 1 loop. If n value is 10, it will run 20 times, if n value is 20, it will run 40 times and so on. Although time complexity increases with 2n, but we discard the constant, and say time complexity is O(n), i.e. time complexity will change linearly with respect to n.

// #2 O(n^2)
sum = 0;
for( i = 0; i < 2n; i++ )
    for( j = 0; j < i; j++ )
         sum++;

Here the outer loop is running 2n times and for each 2n times inner loop will run i times. If you count the operations for different n value, you will see number of times loop runs changes by n^2, not only n. So thatsy time complexity is O(n^2).

// #3 O(n^4)
sum = 0;
for( i = 0; i < n2; i++)
    for( j = 0; j <  i; j++)
          sum++;

Here out loop is running n^2 times and for each outer loop inner loop will run i times(which will be n^2 on average). So outer n^2 X inner n^2 is n^4. So time complexity is O(n^4).

// #4 O(n^5)
sum = 0;
for( i = 0; i < n; i++)
   for( j = 0; j <  i*i; j++)
      for( k = 0; k <  j; k++)
          sum++;

First loop is running n times, 2nd loop is running on average n^2 times(ii is nn), and 3rd loop is running on average n^2 times(j will hold n^2 diff values because of 2nd loop). So total time complexity will be O(n x n^2 x n^2) = O(n^5)

another_CS_guy
  • 682
  • 6
  • 7
0

When analyzing the time complexity, you can ignore all numbers before n, such as 2n is just the same to n. Because when n becomes infinitely large, 2 is just the same to 1. (This is also an important point when analyzing O() complexity)

Take #4 for an example, i is just O(n), j is O(n^2), k is also o(n^2). Then the total complexity will be the multiply for all of them, the answer will be O(n^5). Another example #2, i is just O(n), the same to j, then the answer is O(n^2)

Shawn Jiang
  • 80
  • 11
0

Try to predict how each loop changes sum starting from the inner-most loop. You should be able to arrive at a precise expression that way. E.g. for your second example (I've added an explicit multiplication token, hope that's the correct interpretation here):

sum = 0;
for( i = 0; i <  in pretty much the same way, except for the different series.2 * n; i++ )
    for( j = 0; j < i; j++ )
        sum++;

First replace the inner loop:

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

This is fairly straightforward. There's i iterations and each increments sum by one, so the complete loop can be replaced by sum += i. The outer loop is a bit trickier. We're summing up all integers from 0 to 2 * n, so

sum += 0 + 1 + 2 + ... + 2 * n - 1 + 2 * n

Now there's the well-known formula (or just use either google or wolframalpha, both are good enough to find closed formulas for simple cases like this one)

1 + 2 + ... + n = n * (n + 1) / 2

Using this, we can now also reduce the outer loop:

sum = 0
sum += 2 * n * (2 * n + 1) / 2 = 2*n^2 + n

Now all that remains to do is to remove all lower order terms and coefficients from the expression:

sum = 2 * n^2 + n = O(n^2)