Complexity Evaluation
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums
Results 1 to 2 of 2

Thread: Complexity Evaluation

  1. #1
    Join Date
    Feb 2012

    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)
    return 1;
    for( i=n; i>1; i-- )
    r=r + f( i / 3 );
    return r;

  2. #2
    Join Date
    Feb 2011
    United States

    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,

    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

Windows Mobile Development Center

Click Here to Expand Forum to Full Width

This is a survey!

HTML5 Development Center