Home
> Algorithms, Computer Programming, Computer Science, Problem Solving/Puzzles > Find the complexity of code.

## Find the complexity of code.

I came across measuring complexity of a piece of code, which is really tricky one. Following is the code,

void function( int n)

{

while(n > 1)

n = sqrt (n); // assume sqrt returns square root of any number and ignore the complexity of square root

}

If any one wants to try this do try ๐ and post your answers.

Advertisements

Categories: Algorithms, Computer Programming, Computer Science, Problem Solving/Puzzles

n = n^(1/2)

O( n^(1/2^x) ) … where x is proportional to n again

so O(n)

wait a second…this is logarithmic, and if I am not wrong tightly so

O(log n)

isn’t it?

Hippy. Your answer is not correct.

Mudassir. Your answer is also not correct.

I have already mentioned this is tricky one and not trivial :).

Haroon

Wow, nice query Haroon ๐

well, I did some work out for this algorithm and it is as follow:

(4^1) <= n complexity = O(1)

(4^2) <= n complexity = O(2)

(4^3) <= n complexity = O(3)

(4^4) <= n complexity = O(4)

and so on.

so, I think complexity of this code is O(sizeof(int)-1) or simply O(sizeof(int)).

looking for a good reply ๐

well my comment updated itself,

the work out is as follow:

(4^1) <= n < (4^2), complexity = O(1)

(4^2) <= n < (4^3), complexity = O(2)

(4^3) <= n < (4^4), complexity = O(3)

(4^4) <= n < (4^5), complexity = O(4)

and so on

Hammad your answer is also wrong. Infact I don’t know where are you going by this :)…

Btw Mudassir did it right. He answered me in the email. And I am not sharing the correct answer until some one(now not Mudassir) paste the correct complexity here..:D

What about O(Log(Sqrt(n))) ?

Yaar, atleast tell me if my above answer is wrong? so that I try something else.

Sorry for the late reply Tauseef. Yar you are right to most extent but not accurate. Infact no one has commented right one. If I go for exact complexity than Mudassir’s answer (in an email) is also not correct. Do you think sqrt(n) == lg (n) ??

My guess is O(log(log(n))).

So essentially the code can be regarded as starting with x = 2, computing x = x^2 until you find the first x that is bigger than input n.

So say a = (((2^2)^2)^2), if you do log(a)/log(2) you find out 2*2*2, if do log(log(a)/log(2))/log(2) you find 3, which is the number of times you do the square.

Ziyan, finally some one come up with right answer. Well actually the complexity is a little lesser than lg(lg(n)), which has to be mentioned if we are doing a tighter analysis. But overall you answer is correct one (Y) ๐

Iรm not sure where you’re getting your information, but good topic. I needs to spend some time learning more or understanding more. Thanks for wonderful information I was looking for this info for my mission.

Anyone having a source code that can measure the complexity of a code..