Algorithm Time Analysis: Recursion Case Puzzle

Question

I have a question about a pseudocode algorithm analysis question which involves recursion.

For those that do not know, algorithm analysis generally refers to finding the order of the amount of time it will take for the function to run. So as an easy example, if a function has 2 nested while loops which run from 1 to n, the function will take roughly n^2 time. This is very useful in determining the estimated amount of time a program will take to run. Hopefully that makes sense.

This is an interesting problem involving recursion. Let's begin with the code:

Func3(A,n) {
    if(n <= 10) then return (A[1])
    k = Random(n); //Random returns a number <= n
    s = A[k]; //A constant time operation (negligible amount of time)
    if(k is even) then s = s + Func3(A,n-3); //Referred to as R1 below.
    if(k <= n/2) then s = s + Func3(A,n-9); //Referred to as R2 below.
    return(s);
}

This is an interesting problem because you have to think carefully about the possibilities for k and the fact that k is randomly selected.

Let's take n = 100. Then, what is the worst possible value for k (worst meaning the value which causes the program to run for the longest amount of time)? One may initially think that k=100 will be the worst value, because it will cause both recursions to run the most amount of times due to the small amount for n of n-3 being called from R1. R1 will be hit with n=97, and now there are further possibilities for either R1 or R2 to be hit in the ensuing recursion (keep in mind k is selected randomly EACH time the program runs). It is likely that at least one of them will be hit at each level of the ensuing massive recursive loop, if not both at each level of the loop.

But, this will only cause one of the recursions to run, with the other being neglected. Perhaps the other worst case scenario is that k = 50, which is exactly half of n, and is an even number. Then, both of R1 and R2 are hit on the first run through. Not only does this take twice the amount of time right off the bat, but now both recursions are running and thus there is twice the likelihood of hitting further recursions in the ensuing loops. For example again take n = 100, and k = 50. Then both R1 and R2 are hit with n=97 and n=91, respectively. Now, however, we have 2 recursive loops going and thus there is twice the likelihood of further recursive calls being hit (think: what would happen if for the random selection, K1 = 97, and K2 = 40 in those R1/R2 recursive calls called from the original run thru?).

What is the worst case scenario for the timing here? What is the estimated (using probability ie. chances of R1 = 1/2 while chances of R2 = 1/2) asymptotic running time?

Answer 1

Best case is O(1), worst case is O(n).

The best case is a pretty trivial proof, since the initial n could just be less than ten.

The worst case isn't too hard to prove. Basically, you have to realize that every operation here is proportional to your choice of n. The chance of k being even, or less than n/2, are both of the form O(an), since constants don't actually matter, it's just O(n).

After that, it's just a game of how quickly you number approached a number less than ten. Since you're subtracting constants, and the two conditions don't depend on the size of n, they must also be of the form O(an). Since constants aren't taken into account in big-O notation, you can't possibly do worse than O(n)

Let me know if you've got any questions.