CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    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;
    }

  2. #2
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    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.
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    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.

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured