CODEWITHSUNDEEP
algorithmtime-complexity
Kunal Shrivastava
Kunal Shrivastava

Reputation: 612

Big O of this code

I am doing the exercise of Skiena's book on algorithms and I am stuck in this question:

I need to calculate the big O of the following algorithm:

      function mystery()
      r=0
      for i=1 to n-1 do
         for j=i+1 to n do
            for k=1 to j do
                r=r+1

Here, the big O of the outermost loop will be O(n-1) and the middle loop will be O(n!). Please tell me if I am wrong here.

I am not able to calculate the big O of the innermost loop.

Can anyone please help me with this?

Upvotes: 2

Views: 296

Answers (3)

rliu
rliu

Reputation: 1148

Here's a more rigorous way to approach solving this problem:

Define the run-time of the algorithm to be f(n) since n is our only input. The outer loop tells us this 

f(n) = Sum(g(i,n), 1, n-1)

where Sum(expression, min, max) is the sum of expression from i = min to i = max. Notice that, the expression in this case is an evaluation of g(i, n) with a fixed i (the summation index) and n (the input to f(n)). And we can peel another layer and defineg(i, n):

g(i, n) = Sum(h(j), i+1, n), where i < n

which is the sum of h(j) where j ranges of i+1 to n. Finally we can just define

h(j) = Sum(O(1), 1, j)

since we've assumed that r = r+1 takes time O(1).

Notice at this point that we haven't done any hand-waving, saying stuff like "oh you can just multiply the loops together. The 'innermost operation' is the only one that counts." That statement isn't even true for all algorithms. Here's an example:

for (i = 0; i < n; i++)
{
    for (j = 0; j < n; j++)
    {
        Solve_An_NP_Complete_Problem(n);
        for (k = 0; k < n; k++)
        {
            count++;
        }
    }
}

The above algorithm isn't O(n^3)... it's not even polynomial.

Anyways, now that I've established the superiority of a rigorous evaluation (:D) we need to work our way upwards so we can figure out what the upper bound is for f(n). First, it's easy to see that h(j) is O(j) (just use the definition of Big-Oh). From that we can now rewrite g(i, n) as:

g(i, n) = Sum(O(j), i+1, n)
=> g(i, n) = O(i+1) + O(i+2) + ... O(n-1) + O(n)
=> g(i, n) = O(n^2 - i^2 - 2i - 1) (because we can sum Big-Oh functions 
                                    in this way using lemmas based on 
                                    the definition of Big-Oh) 
=> g(i, n) = O(n^2) (because g(i, n) is only defined for i < n. Also, note
                     that before this step we had a Theta bound, which is 
                     stronger!)

And so we can rewrite f(n) as:

f(n) = Sum(O(n^2), 1, n-1)
=> f(n) = (n-1)*O(n^2) 
=> f(n) = O(n^3)

You might consider proving the lower bound to show that f(n) = Theta(n^3). The trick there is note simplifying g(i, n) = O(n^2) but keeping the tight bound when computing f(n). It requires some ugly algebra, but I'm pretty sure (i.e. I haven't actually done it) that you will be able to prove f(n) = Omega(n^3) as well (or just Theta(n^3) directly if you're really meticulous).

Upvotes: 2

Rubens
Rubens

Reputation: 14778

The analysis takes place as follows:

  • the outer loop goes from i = [1, n - 1], so the program would have linear complexity O(i) = O(n) if, inside this loop, only constant operations were performed;
  • however, inside the first loop, for each i, some operation is executed n times -- starting from j = [i + 1, n - 1]. This gives a total complexity of O(i * j) = O(n * n) = O(n^2);
  • finally, the innermost loop will be executed, for each i, and for each j, k times, with k ranging from k = [j, n - 1]. As j begins with i + 1 = 1 + 1, k is assymptotically equal to n, which gives you O(i * j * k) = O(n * n * n) = O(n^3).

The complexity of the program itself corresponds to the number of iterations of your innermost operations -- or the sums of complexities of innermost operations. If you had:

for i = 1:n

    for j = 1:n

        --> innermost operation (executed n^2 times)

        for k = 1:n
            --> innermost operation (executed n^3 times)
        endfor

        for l = 1:n
            --> innermost operation (executed n^3 times)
        endfor

    endfor

endfor

The total complexity would be given as O(n^2) + O(n^3) + O(n^3), which is equal to max(O(n^2), O(n^3), O(n^3)), or O(n^3).

Upvotes: 2

krom
krom

Reputation: 36

It cannot be factorial. For example if u have two nested cycles the big O will be n^2, not n^n. So three cycles cannot give more than n^3. Keep digging ;)

Upvotes: 1

Related Questions