Find worst-case Big-oh runtime

[dendritic]

After reading many articles, pdfs, and other resources about Big-Oh notation and runtime complexities, I'm still having a difficult time with runtime analysis and proofs.

I even went to several tutors who did not know how to explain the runtime complexities for the code below, and got mixed answers: O(N^2), O(2n-1), or O(2^logN). Even my TA for this course doesn't know..

But this is how I'm reading it..

int F(int a[], int n) {
   int x=0, i, j;
   for(i=1; i<n; i=i*2){   //<-- LogN times
      for(j=0; j<i; j++)   //<-- N times? This is where I'm having trouble
         x += a[j];
      }
     return x;
}

With that, I assumed that the runtime was O(N*logN), but it's probably wrong anyways. Could anyone please walkthrough this problem for me step by step? And maybe links to great resources for understanding Big-Oh complexities, etc.

Thank you.

[Bdanielz]

Let me give you another answer :/ (sorry maybe someone smart will jump in here) I am probably making all this up...

int F(int a[], int n) {
   int x=0, i, j;
   for(i=1; i<n; i=i*2){   //<-- LogN because if n = 4 this would run 2 times 
      for(j=0; j<i; j++)   //<-- i = 2*i or i^2; rewriting i as n then = n ^2 
         x += a[j];
      }
     return x;
}

putting it together
Worse Case = Log(2,n) * n^2 = (n^2 log(n))/(log(2))
http://www.wolframalpha.com/input/?i=Log%282%2Cn%29+*+n^2+

[MiiNiPaa]

@Bdanielz OP was right in his analysis of outer loop
See for yourself:

n = 10: 4 iterations
n = 100: 6 iterations
n = 1000: 9 iterations
n = 10000: 13 iteration

Clear logarithmich scale.

He was actually right with his inner loop analythis too, it is O(N). It is derived from sum of geometric series formula:

Mean run time is sum of all runs / number of runs:

(1 - 2(log2N)) / (1 - 2) / log2N
(1 - N) / -log2N

As logN if quickly made irrelevant by quickly growing N, it s final complexity is O(N).

So total co,plexity is O(logN)×O(N) = O(NlogN)

EDIT: Bdanielz, it seems that you fixed your post and made first part of my irrelevant. Still you cannot just replace i with n, you need to analythe actual amount of iterations.

Edit 2: See JLBorges answer, it is correct one

[Bdanielz]

Thanks - you are looking at my third edit now...
I started to answer before I really looked at the problem.

[MiiNiPaa]

It is almost correct now. Still inner loop does not have complexity O(N²). In any unknown situation use empiric method: http://puu.sh/k9ya2/c3fe6f8684.png. You can see that it is linear complexity. Now remember that in asymptotic analysis constants are irrelevant and can be thrown out ( O(2N) == O(N) ) and you will have canonical answer.

[JLBorges]

> I even went to several tutors who did not know how to explain the runtime complexities for the code below,
> and got mixed answers: O(N^2), O(2n-1), or O(2^logN)

O(2n-1) is the right answer. Or in Big-Oh, O(n).

We can easily test it out (for powers of two):

#include <iostream>
#include <iomanip>

int cnt = 0 ;

int f( int a[], int n )
{
    int x=0, i, j;
    for(i=1; i<n; i=i*2) // this loop executes for i == 1, 2, 4, 8, 16, 32 ... n-1
    {
        for(j=0; j<i; j++) // each time, this loop executes i times
                           // the total number of times this loop executes is therefore:
                           // i times each time, for i == 1, 2, 4, 8, 16, 32, .. n-1
                           // ie. 1 + 2 + 4 + 8 + 16 + 32 + ... + (n-1)
                           // ie. 2 ^ log(n-1)  (note: this step is easy if we recall binary representation of integers)
                           // ie. n-1
                           // complexity of the algorithm is O(n-1)
                           // or in asymptotic notation: O(n)
        {
            x += a[j];
            ++cnt ;
        }
        ++n ;
    }
    return x;
}

template < int N  > struct test : test<N/2>
{
    test()
    {
        cnt = 0 ;
        int a[N] {} ;
        f( a, N ) ;
        std::cout << std::setw(10) << N << std::setw(10) << cnt
                  << std::setw(10) << (2*N)-1 << '\n' ;
    }
};

template <> struct test<1> {};

int main()
{
    std::cout << std::setw(10) << "   N"  << std::setw(10) << "   cnt"
              << std::setw(10) << "      (2*N)-1" << "\n----------------------------------\n" ;
   test<1024*1024>() ;
}

         N       cnt      (2*N)-1
----------------------------------
         2         3         3
         4         7         7
         8        15        15
        16        31        31
        32        63        63
        64       127       127
       128       255       255
       256       511       511
       512      1023      1023
      1024      2047      2047
      2048      4095      4095
      4096      8191      8191
      8192     16383     16383
     16384     32767     32767
     32768     65535     65535
     65536    131071    131071
    131072    262143    262143
    262144    524287    524287
    524288   1048575   1048575
   1048576   2097151   2097151

http://coliru.stacked-crooked.com/a/732a353c529c932a

[MiiNiPaa]

JLBorges is right. I noticed it after I went AFK, so I could not change it right away.

As logN if quickly made irrelevant by quickly growing N,

This is my mistake. You should not remove multiplier.
Inner loop complexity is O( N/logN ) and total is O(logN×N / logN) or O(N)

You can even check it by deriving a formula describing amount of iterations:
it is 2^log₂N + 2^{log₂N - 1} + ...
Which is N + N/2 + N/4 ...
You can find sum of this series and see for yourself.