Big O notation and recursive functions

[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 the 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!

[hamsterman]

big O notation shows how fast the required time to use the functiom grows when number of elements increases.
the function in your code will never stop calling itself, so the time taken is infinite (except that there will be a stack overflow). I suppose that would mean constant time :)

[ghostfacelz]

I might have over simplified.
The recursive function will call itself up to a maximum of 17 times - but average at about 5.

[simeonz]

Unfortunately, the rules are much harder than that. It is not the number of nested loops that matters, but the form of the recursive call, the number of iterations each loop will have (with respect to the previous one, with respect to the arguments of the function.) There are a bunch of theorems that you can learn, but you can also forget them as easily :) (They cover the most popular cases.)

Regards

[ghostfacelz]

Thanks for the reply.
The nested loops are to iterate over a 2D array of letters (in my case its a 4x4 grid).
Would you happen to know where I can take a look at these theorems. As I said earlier, I scoured the internets in search of something that could help me make some sense to no avail.
Maybe I can come up with something that "looks" right...

[simeonz]

Ok, google seems to open to words like recurrence, complexity, master, theorem. I tried "recurrence complexity theorem" and "recurrence complexity master theorem".

Here are some very random picks, but still sources that seemed reasonable (considering the subject matter.)

I liked this: http://www.inf.usi.ch/carzaniga/edu/algo08f/recurrence.pdf
and this site offers a doc file under the link "Master Theorem for time complexity of Recurrence relations" that offers an extremely brief summary: http://www.cs.ucf.edu/courses/cop3503h/fall06/lectures.html

Both deal with divide and conquer type of solutions with sub-polynomial post-processing time. That is, you will be able to apply them if:
- your solution is of the type that reduces the original problem to a fixed number of sub-problems
- the size of a sub-problem remains in fixed proportion to the size of the original problem for all levels of the recursion
- the pre-processing and post-processing time required for producing the sub-problems and combining their solutions has sub-polynomial order of growth in terms of the original problem size

The formalism is:
T(n) = a T(n/b) + O(n^k), where "a" is the number of sub-problems, "b" is the divisor of the original size, and the production+combination steps require sub-"n^k"-polynomial time. Note that you may require to solve 3 sub-problems (a = 3), each of size one half (b = 2), to conclude that some of the sub-problems may overlap.

To get a taste at some more general treatment, I think you can take a look at this: http://www.it.uu.se/edu/course/homepage/datastruk/ht06/tut1.pdf

And, of course, wikipedia: http://en.wikipedia.org/wiki/Master_theorem

PS: I am not sure that your case falls in the above categories.

Regards

[ghostfacelz]

Thanks simeonz!!

Some of that shed alittle light. I just hate proofs :P
in any case, from what research I have done, here is kind of where I am at:

the recursion function is O(N) on its own, based upon how many calls it receives (max=17)
In addition, because there are 2 nested loops, O(n)+O(n)+O(n) = O(n^3)

Adding the solve function
Solve = O(1) + the while which will have N inputs, the 2 for loops which depend on N. So we have another function that is n^3 + the recursion function which is another n^3.

so i believe the overall algorithm would be O(n^6)
I might be generalizing a bit, but I think it makes sense... any thoughts?

[simeonz]

May be your intuition is right (and not so much the formalism). Bit rusty myself though.

the recursion function is O(N) on its own, based upon how many calls it receives (max=17)

I don't understand. What if it received 18 calls? I mean, would that be different? What is N (the problem size) here?

O(n)+O(n)+O(n) = O(n^3)

Probably you meant O(n)xO(n)xO(n) = O(n^3).

so i believe the overall algorithm would be O(n^6)

It is possible. However, such algorithm would be extremely slow in practice. You could not run it for more than a size 100 input (whatever that is in your case).

I am not certain that I could help you, but in order to actually try to reason on the complexity of something, I need more information. Let's take on the recursiveFunction for starters.

- What is the problem size for recursiveFunction (i.e. some characteristic of the input that could be arbitrarily large, although you may keep it fixed for testing?)

- How much iterations the first loop performs with respect to thus defined problem size?

- Is the problem size of the inner loop the same, or does the inner loop solve a task that has a different (smaller) problem size (and how does it change for each iteration of the outer loop)?

- What is the problem (size) passed down in the recursive call?

You may be right. But I still need more data to discuss this.

Regards

[imi]

O(n^6) is probably correct. Its only correct if your recursive call condition is not dependend from N.


Simplified: When calculating the big-O notation, a recursive call that is independend of any big-O-variable count as the amount the function would have without the recursion. There is no additional O(n) for the "recursion on its own" involved. (where should this come from? Any normal function call is just O(1) and a recursive call is just a function call in the end.)


In this case you have:
- 2 cascaded for-loops in solveFunction
- within that another 2 cascaded for loops in recursiveFunction.
- finally another 2 cascaded for loops for the recursion of recursiveFunction.

Since all are cascaded into each other, they are multiplied: O(n^2) * O(n^2) * O(n^2) = O(n^6)


The long story is, that this is only true if the recursion condition is O(1), in other words: the number of times the function calls itself is negletable and not dependend of any big-O-variable. You said, if the function calls itself 5 times, so the cost would be actually O(5), but in typical big-O-notations, constants are skiped out.

You can not skip out this, if the number of self recursions is dependend from N. An very typical example where the recursion condition is dependend is binary search. Take an classic recursive binary search algorithm:

// don't take this too seriously: there are probably tons of bugs in this code ;)
bool binarySearch(int start, int end, int value)
{
  if (start == end) return false; // no place to search left
  pivot = searchData[start + (end-start)/2]; // look at the middle of our search data
  if (value == pivot) return true; // found the value
  if (value < pivot) return binarySearch(start, end/2, value); // its in the lower half
  return binarySearch(start + (end-start+1)/2, end, value); // its in the upper half
}

This is a recursive function too, containing no loop at all, but if the size of the search data here is not neglatable, the condition under which the function calls itself is not neglatable either! Instead, it depends on the number of calls to the function already done. On the first call its almost certain calls itself again, only 1 out of N times (if N is the size of the search data) it does not call itself. On second iteration, this probability is doubled, then doubled again and so on. Hence, you end up with the well-known O(log(N)) for binary search.

Ciao, Imi.


PS: Also, in your example you assume that the While-loop is O(1). This means the number of iterations until eof is true is negletable! If your while loop does loop approximately the same times as your for loops (depends on the same magnitude of iterations as the for loop), then it becomes O(n^7).

PPS: O(n^6) or O(n^7) is only true, if all the for loops are looping over the same (non-neglatable) size. Simple counter example: If one of the loops looks like for (int i = 0; i < 2; ++i) then it clearly does not contribute another O(n), but only O(2) (which usually is simplified to O(1))

[ghostfacelz]

I guess I may have left out too much in my original code.
Here it is again with the relevant bits added in:

void solveFunction(variables) {
while(!words.eof()) { //reads in a wordlist - any size - im using one that 176,000
            for () { //working our way through a 2d array - will always be 4x4
                for () {
                   recursiveFunction(variables=current cell from 2d array, index)
                        }
                    }
             }
}

bool recursiveFunction (variables) {
if index == word.length() return true //terminates recursion
for () { //goes through 2d array - 3x3 (the cells surrounding cell from calling function)
    for () {
           recursiveFunction(current cell, index)
            }
        }
}

word length will never be more than 17, so that will be the maximum times the recursive function will be called.
i left out the index calculation logic since its not really relevant....

@Imi - 1) Thanks for the reply based on what you have said, I think i am off in my calculation.
2) It might be a language barrier, but what do you mean by "neglatable"
3) since my for loops are a fixed size (they iterate over a 4x4 array and a 3x3 array), i think that my previously calculated O(N)'s should infact be O(4) and O(3) respectively...and simplified to O(1).

That said, here is where I am at now:
Solve function gets called once - O(1)
Inside solve function we have a while loop that runs through a word list - should be O(N)
Nested inside that we have 2 nested for loops of fixed size - O(4) & O(4)
----this is one area I am unsure about, for each word in the word list, the outer loop runs 4 times and the inner loop runs 16 times. Shouldnt this be a O(N^2)?
Moving on we come to our recursive function...

recursiveFunction worst case runs up to 17 times - O(17)
inside we have another set of nested for loops, O(3) & O(3)
Again, since they are nested, it feels odd that it wouldnt be an O(N^2)...
Some recursion index logic happens
then we decide if we call the recursive function again.

[simeonz]

Actually, there are two characteristics here that can be called "size". There could be many more, but I will focus on two.

First, I believe that by problem size you mean the number of words in the dictionary. Lets call it N. Here is the punch line. The execution time of recursiveFunction does not depend on N at all. I mean, it only chews some information out of a single word. How slow it does that? Here you find the second problem size. The maximum length of a word. Lets call it M.

As I said, the time for executing recursiveFunction does not depend on N, but it is a function of M. Here is the recurrence expression for it:
T(M) = 9 * T(M-1) + c
The time for processing a word of size M includes the time necessary for processing 9 times a word of size M-1 and some time that is spent in the constant number of loop iterations inside the function.
T(0) = c
This is the time for handling the base case - the bottom of the recursion.

Now, if I did ignore the constant above, I could write the formula for T(M) as
T(M) = 9 * T(M-1)
T(0) = c
, which is exactly the definition for the exponential function "c (9 ^ M)".

If I add the constant I get approximately the same, because
T(M) =
= 9 T(M-1) + c =
= (9 ^ 2) T(M-2) + 9 c + c =
= 9 ^ M + (9 ^ (M-1)) c + (9 ^ (M-2)) c + ... + (9 ^ 2) c + 9 c + c =
(as geometric progression) = 9 ^ M + c ((9 ^ M) - 1) / (9 - 1) =
= const 9 ^ M + const =
= O(9 ^ M) (actually theta (9^M))

Ok, at some places I have been a bit sloppy. But that's it. So the recursiveFunction is exponential in the size of the words.

The solveFunction has execution time that depends on both N and M. But here everything is simple. The loop processes every word once with recursiveFunction. Let's call the execution time for solveFunction L(M, N).

L(M, N) = L(M, N-1) + 16 T(M)
L(0, N) = c

You can prove by induction, that L(M, N) = 16 N T(M). So in the end you get that the execution time for solveFunction is O(N * (9 ^ M)). If you assume that the length of the words in the dictionary is bound from above (i.e. it will never scale beyond 17), then the execution time is O(N).

As you see, the concept behind execution times is recurrences. If you can solve recurrences, you can also investigate asymptotic complexity of algorithms. The so called "master theorem" handles some non-obvious cases of recurrence, but the one above are classic recursive definitions of famous math formulas. Like:
f(n) = a f(n-1), f(0) = 1 is the exponential function a ^ n
g(n) = g(n-1) + b, g(0) = 0 is the linear function b * n
The above are just slightly different cases.

Regards

[ghostfacelz]

This could be why I was having such difficulty figuring it out (that and I know next to nothing regarding big o notation)
Thinking in terms of 1 input - N - doesnt really work for the whole algorithm since the recursive function is dependent on the size of the word where the solve function is dependent on the amount of words.
Hence you have O(N) for the amount of words and O(M) for the word size.

This actually makes a lot of sense now...

I have seen some big o notation examples, but have never seen one where there are 2 variables in the notation (in this case, N and M)
Is it fairly common to have multiple variables depending on the case? Or is there a way to further simplify / combine the notation into one overarching big o notation for N?

(also, thanks for the help! Reading about it only does so much, having an actual discussion with someone who knows what they are talking about really helps a lot!)

[simeonz]

I have seen some big o notation examples, but have never seen one where there are 2 variables in the notation (in this case, N and M)
Is it fairly common to have multiple variables depending on the case?

They appear sometimes in graph algorithms, computational geometry, partial sorting, etc. But algorithms are not systems, just system elements. They are relatively simple and possess fewer aspects.

Sometimes a lot of "sizes" disappear from the final analysis. Some of them are simply ignored on pragmatic grounds and others are subsumed from the calculations, because under the specific assumptions, they are dominated, or dependent. Basically, single variable complexity results are very streamlined.

Or is there a way to further simplify / combine the notation into one overarching big o notation for N?

You mean, a method that gives you the innate "size" characteristic for a given problem that will make your results universally meaningful? Not any that I know. Well, you could use the entropy of the data, or model the input in abstract machine, etc. The applicability is limited.

Consider your case. The algorithm is exponential with respect to the total length of the dictionary in bytes (MN). In the worst case the dictionary contains just one word, and the size of the dictionary contributes exclusively to the length of a single word. The result is overly pessimistic and will misinform. To remedy this, you are forced to make educated guess about the relevant "sizes".

Regards

[ghostfacelz]

Thanks again simeonz!
This has been very educational. I have a much better grasp on the concept now.

-G