February 1st, 2012, 12:21 AM
What is the complexity of the below code? I could not not frame the recurrence leading to the code,it will be helpful if you guys please get me atleast the method to structure its recurrence:
Here it goes:
for( i=n; i>1; i-- )
r=r + f( i / 3 );
February 27th, 2012, 12:14 AM
Re: Complexity Evaluation
A bit late, but the key insight is that you can express the solution as a recurrence relationship. Namely the complexity for some value of n (let's call it C(n)) is:
C(n) = n * C(n/3) subject to C(1) = 1
This is because the loop runs n times with worst-case complexity of C(n/3) per iteration.
Actually this is an overestimate. The real complexity relationship is:
C(n) = Sum[ C(i/3) ] for i in [1, n]
but this will be a pain to deal with. The overestimate will be reasonable.
All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.
Click Here to Expand Forum to Full Width