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?
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²)
Prove for the sum of series [ 1 + (1/3) + (1/3)² + (1/3²)² + (1/3³)²..... ]
, is below.