Clever Geek Handbook

What is the time complexity of the next function?

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

In my opinion the appropriate repetition would be:

Recurence relatio

The solution to this problem ...

Input Substitute 1

The function becomes

Rest of the image

Can you check and fix the solution?

+3


source to share


3 answers


you are right 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))
+2


source


Your conclusion is wrong in the first step!

Now, after going through your steps, your recurrent equation is wrong.

The recurrent will be ---> T(n) = a ⋅ T(n / b) + f(n)

, here: a = 1, b = 2 and f (n) = log n (since n is sequentially stored on the stack and decrements each time by half, whereas you assumed f (n) to be 1 // THIS IS THE SOURCE OF THE ERROR!

T(2^m)=T(2^(m/2))+m

// Refine your steps.

S(m)=S(m/2)+log m

// Improve your steps

When solving this equation using master theorem

--- it will fall under the second formula of the main theorem as

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



you will get solution like 0(log (m)).

S(m) = O(log m)

Then, when increasing to power T(2^(m))=O(log m)

, which will then give

Now, replacing the value of m as (m=log 2 (n))

back in this equation, you get

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

...

I hope this is very clear. Feel free to comment if you cannot understand a step ...

+1


source


You can rely on a methodology like this to solve this problem:

enter image description here

+1


source






More articles:


All Articles