Calculating Time Complexity of a Recusive Algorithm?

Take a look at the Master Theorem . You can treat this as a "divide and conquer" algorithm.

Up vote 2 down vote favorite 1 share g+ share fb share tw.

I'm trying to calculate the time complexity of a recursive algorithm and I think I've almost got it. Here's the psuedocode I've been looking at: long pow( long x, int n ) { if (n == 0) return 1; if (n == 1) return x; if(isEven(n)) return pow(x, n / 2 ) * pow(x, n / 2); else return x * pow(x * x, n / 2); } isEven merely determines whether or not the integer passed to it is even or not, and for the point of this example, operates in constant time. So, if n = 0 or n = 1, it operates it has constant time operation, like this: f(n) = C0.

However, when n > 1, it should operate like so: f(n)= f(n-1) + f(n-1) + C1 when n is even and f(n)= f(n-1) + 1 when n is odd, correct? Or should it be: f(n)= f(n/2) + f(n/2) + C1 when n is even and f(n)= f(n/2) + 1 when n is odd? I've been looking at a lot of examples.

Here is one I've found very helpful. My problem stems from there being two recursive calls when n is even- I'm not fully sure what to do here. If anyone could point me in the right direction I'd really appreciate it.

Algorithm homework big-o time-complexity link|improve this question asked Feb 1 '11 at 2:32thomascirca1558 96% accept rate.

Allow me to welcome you to StackOverflow and remind three things we usually do here: 1) As you receive help, try to give it too answering questions in your area of expertise 2) Read the FAQs 3) When you see good Q&A, vote them upusing the gray triangles, as the credibility of the system is based on the reputation that users gain by sharing their knowledge. Also remember to accept the answer that better solves your problem, if any, by pressing the checkmark sign – belisarius Feb 1 '11 at 4:24 2 This newbie question is well asked. – sharptooth Feb 1 '11 at 13:00.

Take a look at the Master Theorem. You can treat this as a "divide and conquer" algorithm. The end result is that with the two recursive calls in place, you end up with a worst case O(n) runtime.

E.g. Pow(x, 4) calls pow(x, 2) twice, and pow(x, 1) four times; in general a power of two will result in n*2-1 calls. Also note that by just calling pow(x, n/2) once and squaring the result in that branch, the algorithm becomes O(log n).

Thanks. I've been looking at the Master Theorem a bit and I'm trying to wrap my head around it... guess I'll have to give it a bit more thought! – thomascirca Feb 1 '11 at 2:59 Don't feel too bad -- it's one of the hardest bits you need in the runtime analysis of most common-case code you see.

– Walter Mundt Feb 1 '11 at 3:02.

Let's define f(m) as that it gives you the number of operations of a problem with size m. The 'problem' is of course exponentiation (pow), like x^n or pow(x,n). The long pow( long x, int n ) { function does not need to do more or less work if I change x.

So, the size of the problem exponentiation does not depend on x. It does however depend on n. Let's say 2^4 is of size 4 and 3^120 is of size 120.

(Makes sense if you see that 2^4=2*2*2*2 and 3^120=3*3*3*3*..*3) The problem size is thus equal to n, the second parameter. We could, if you want, say the problem size is 2*log(n), but that would be silly. Now we have f(m) is the number of operations to calculate pow(x,m) for any x.

Because pow(x,m) is exactly the problem with size m. So, if we have pow(x,y) then the number of operations is, by definition, f(y). For example, pow(3,3*m/2) has f(3*m/2) operations.

Finally, let's count the operations long pow( long x, int n ) { if (n == 0) //1 return 1; if (n == 1) //1 return x; if(isEven(n)) //1 return pow(x, n / 2 ) * //that is f(n/2), y=n / 2 pow(x, n / 2); //also f(n/2) else return x * pow(x * x, n / 2); //1+1+f(n/2) } Taking it together: f(n) = 2*f(n/2) + c1 (n even) and f(n) = f(n/2) + c2 (n odd). If you are only interested in the worst case scenario, then note that the odd case is less work. Thus f(n) is bounded above by the even case: f(n).

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.