CODEWITHSUNDEEP
performancealgorithmfunctional-programmingtime-complexity
Scorpious
Scorpious

Reputation: 133

What is Time Complexity of the following function?

int DoSomething(int n) {
    if(n < 2) return 1;
    else return DoSomething(floor(sqrt(n))) + n;
}

According to me the corresponding recurrence will be :

Recurence Relatio

Solving this recurence...

Putting Substitute 1

The function becomes

Rest of the image

Can you please verify & rectify the solution?

Upvotes: 3

Views: 2322

Answers (3)

Vikram Bhat
Vikram Bhat

Reputation: 6246

you are correct upto :-

S(m) = O(log(m))

then

T(2^m) = O(log(m))

n = 2^m

T(n) = O(log(m))

but m = log(n)

hence 

T(n) = log(log(n))

Upvotes: 2

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

You can rely on such a methodology to solve it:

enter image description here

Upvotes: 1

Am_I_Helpful
Am_I_Helpful

Reputation: 19158

Your derivation is wrong at the very first step !

Now,going through your steps, your recurrence equation is wrong.

The recurrence will be of the form--->T(n) = a ⋅ T(n / b) + f(n),here, a=1,b=2, and f(n)=log n(because n is getting stored successively in stack and it is decrementing each time by half, whereas you have assumed f(n) as 1 // THIS IS THE SOURCE OF ERROR!

T(2^m)=T(2^(m/2))+m // Improve your steps.

S(m)=S(m/2)+log m // Improve your steps

On solving this equation using master theorem---it'll come under second formula of master theorem as

f(n) ~= log n ~= 1 == 0(n^log 2 (1)) == 0(n^0) ==1 // ,most important step,if unclear,please ask...

, you'll get solution as 0(log (m)).

S(m) = O(log m)

Next, on raising to the power, T(2^(m))=O(log m) which will further yield

Now,substituting the value of m as (m=log 2 (n)) back in this equation, you'll get

T(n)=O(log ( log (n))).

I hope this is much clear.Feel free to comment if you couldn't understand any step...

Upvotes: 1

Related Questions