Big O and recursion

[ghostfacelz]

Hi,

I have read about 30 websites, and several articles on the topic, but nothing has really done a good job of explaining how to calculate the big o of a recursive function. Hopefully someone here might be able to offer some insight.

Here is a quick outline of my code.

void solveFunction(variables) {
while(!eof) {
            for () {
                for () {
                   recursiveFunction()
                         }
                      }
                   }
}

bool recursiveFunction (variables) {
for () {
    for () {
           recursiveFunction()
             }
         }
}

So based on what I have read, my while loop is O(1) + 2 for loops = O(n^2) + the recursive function.
The recursive function alone is O(n^2) + recursive function.
Can anyone tell me if im on the right track, what I might be doing wrong, and help me figure out what the big o of this might be?
I am really at a loss and any help would be greatly appreciated.
Thanks!

[nuzzle]

some insight.

The Big-O measure is a broad classification of algorithms. It tells you how the algorithm will respond to a change in input load. But not in any greater detail, just the order of magnitude.

Informally you can think of it like this: Say the input to the algorithm (the N) gets doubled, how much longer will the algorithm then take to finish? If it takes the same you have an algorithm with constant complexity that is an O(1) algorithm. If it takes twice as long the algorithm is linear in complexity and you have an O(N) algorithm. If it takes 4 times as long the algorithm is quadratic and you have an O(N^2) algorithm. And so on.

In your recursiveFunction example you need to define the N. You then need to analyze how the recursive function reacts to a change in N. Your example is lacking this necessary information. But say you have something like this.

bool recursiveFunction (int n) {
  if (n<N) { // recursion terminates after N calls (is linearly dependent on N)
     for () { // loop is proportional to N
         for () { loop is proportional to N
              recursiveFunction(n+1);
         }
     }
  }
}

In this case if N is doubled, you get twice as many recursive calls so the recursion alone is O(N). And each time the recursive function is called, the two loops will get executed, each making an O(N) contribution. Since everything is nested the overall algorithm will be O(N^3).

If you now analyze solveFunction in a similar way you get,

void solveFunction(variables) {
   while(!eof) { // there are N inputs
        for () { // loop is proportional to N
              for () { // loop is proportional to N
                  recursiveFunction(0) // known to be O(N^3)
              }
           }
     }
}

Since again everything is nested this gives a total complexity of O(N^6). It means that if N is doubled, the algorithm will take in the order of 2^6 times longer to complete.

[ghostfacelz]

Thanks nuzzle!!!
That really helps. It kind of clicked right there.
The recursive function will fire at most 17 times.
So I should be able to figure it out from there.
Really, thanks for breaking it down for me, I was really struggling there
Classification wise, ( O(logn), O(n^2), O(2n), etc...) this one is pretty high up there at O(n^6), but at least its not a 2^n

**Edit: The more I read over it, the more it makes sense. Thanks again!

[nuzzle]

Thanks nuzzle!!!
That really helps. It kind of clicked right there.
The recursive function will fire at most 17 times.
So I should be able to figure it out from there.
Really, thanks for breaking it down for me, I was really struggling there
Classification wise, ( O(logn), O(n^2), O(2n), etc...) this one is pretty high up there at O(n^6), but at least its not a 2^n

**Edit: The more I read over it, the more it makes sense. Thanks again!

Glad it helped.

Note that if the recursive function always fires at the most 17 times regardles of N, then it has a constant complexity contribution, that is O(1).

Recursion usually leads to O(logN) complexity. You usually get that when you apply the divide-and-conquer principle to a problem, such as a binary search of a sorted array. Another example is when you search tree based data structures such as std::map in C++ and TreeMap in Java.

The most common example of O(1) complexity is hash table based searches. In C++ there's the std::tr1::unordered_map and in Java the HashMap for example.

You're right that O(N^6) is quite much especially if it's the overall complexity of a whole program. What you aim for is at most O(N). This means that if the workload doubles the program takes twice as long to finish, something most consider acceptable behaviour.

I've often been asked to optimize programs which unexpectedly get very much slower when the input load is increased by just a little. In 9 cases out of 10 the problem is a performance bottleneck which in principle looks like this,

for() { // O(N)
   for() { // O(N)
      // here you have O(N^2)
   }
}

And in 9 cases out of 10 the solution is to replace the innermost O(N) loop with look-ups in a hash based data structure so you get O(1) complexity there, like

for() { // O(N)
   hashed_look_up() { // now O(1)
      // here you have O(N) only
   }
}

Now the program behaves much better. If you want to reach guru programmer status or have a successful consulting carrer you should remember this.

[ghostfacelz]

for() { // O(N)
   hashed_look_up() { // now O(1)
      // here you have O(N) only
   }
}

Now the program behaves much better. If you want to reach guru programmer status or have a successful consulting carrer you should remember this.

Havent had too much experience with hash tables or lookups (none actually), so this is something I will definitely look into.
Thanks again!

-G