CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member Join Date
Feb 2012
Posts
1

## Complexity Evaluation

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:

int f(n)
{
if(n<=1)
return 1;
else
for( i=n; i>1; i-- )
{
r=r + f( i / 3 );
}
return r;
}  Reply With Quote

2. ## 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.  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
• 