Search code examples
algorithmloopswhile-looptime-complexitylogarithm

what is the complexity of this algorithm , can i sum it to infinity?


Func(n)
{
   i = n
   while(i>=1)
      g(i);
      i = i/3;
}

what is the complexity of this algorithm? (while the complexity of g(n) is theta(n²)) I assumed for bigger n's you say that the complexity is

n² + (n/3)² + (n/3²)² + (n/3³)²..... to infinity.

And the answer is theta(n²). Is that true?


Solution

  • Lets look at the series that we have got in our hands.

    => n² + (n²/3) + (n/3)² + (n/3²)² + (n/3³)²..... 
    taking n² common
    => n² * [ 1 + (1/3) + (1/3)² + (1/3²)² + (1/3³)²..... ]
    

    As [ 1 + (1/3) + (1/3)² + (1/3²)² + (1/3³)²..... ] is a decreasing series, it is equal to 1.

    Thus the answer is O(n²)


    EDIT 1:

    Prove for the sum of series [ 1 + (1/3) + (1/3)² + (1/3²)² + (1/3³)²..... ], is below.

    enter image description here