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.
n = n^(1/2)
O( n^(1/2^x) ) … where x is proportional to n again
so O(n)
By: hippy on October 30, 2008
at 12:05 am
wait a second…this is logarithmic, and if I am not wrong tightly so
O(log n)
isn’t it?
By: mudassir on October 30, 2008
at 4:52 pm
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
By: Haroon Saeed on October 31, 2008
at 2:49 am
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
By: Rana Hammad on November 4, 2008
at 1:13 pm
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
By: Rana Hammad on November 4, 2008
at 1:16 pm
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
By: Haroon Saeed on November 4, 2008
at 3:26 pm
What about O(Log(Sqrt(n))) ?
By: Touseef Liaqat on November 6, 2008
at 5:24 am
Yaar, atleast tell me if my above answer is wrong? so that I try something else.
By: Touseef Liaqat on November 14, 2008
at 4:50 pm
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) ??
By: Haroon Saeed on November 16, 2008
at 10:09 am
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.
By: Ziyan on November 24, 2008
at 5:28 am
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)
By: Haroon Saeed on November 24, 2008
at 5:33 am