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.
Categories: Algorithms, Computer Programming, Computer Science, Problem Solving/Puzzles
Leave a reply to Haroon Saeed Cancel reply
Haroon Saeed’s Shared Google Reader
- An error has occurred; the feed is probably down. Try again later.
Haroon Saeed's Weblog.. 
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..