0

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?

Improve this question
2
  • Can you fix you pseudocode so it could potentially work? Alternately could you include an example of A? Commented Feb 4, 2014 at 1:32
  • 'A' is simply an arbitrary array, it does not matter what the length is as long as it is greater than or equal to n. I believe A is negligible in determining the problem and could be removed from the problem as a whole, including the line s = A[k];. It is just showing that there is some actual constant time operation going on in the program, instead of only recursion. Commented Feb 4, 2014 at 1:35

1 Answer 1

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Yes, that makes sense. I suspected as well that it should be in n time, because even if both recursions are running they are both reducing by a constant amount each time. It doesn't even matter which of R1 or R2 runs (or even both) because that would just be multiplying some negligible constants by n (we don't even really need to know what they are, although n will be divided by 3 or 9). At least that's how I am beginning to wrap my head around it.
@Musicode Worth noting that recursive loops don't run concurrently. Your first finishes, then you'd move on to the second. Also don't forget to accept an answer if it's been helpful.
Yes I suppose you are right, especially when considering how recursion aligns in the memory stack anyway. I always think about it as if they run concurrently, but they don't. Thank you for your help.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.