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.

  1. hippy
    October 30, 2008 at 12:05 am

    n = n^(1/2)

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

    so O(n)

  2. October 30, 2008 at 4:52 pm

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

    O(log n)

    isn’t it?

  3. October 31, 2008 at 2:49 am

    Hippy. Your answer is not correct.

    Mudassir. Your answer is also not correct.

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


  4. November 4, 2008 at 1:13 pm

    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 ๐Ÿ˜‰

  5. November 4, 2008 at 1:16 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

  6. November 4, 2008 at 3:26 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

  7. Touseef Liaqat
    November 6, 2008 at 5:24 am

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

  8. Touseef Liaqat
    November 14, 2008 at 4:50 pm

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

  9. November 16, 2008 at 10:09 am

    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) ??

  10. November 24, 2008 at 5:28 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.

  11. November 24, 2008 at 5:33 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) ๐Ÿ™‚

  12. May 3, 2013 at 2:09 am

    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.

  13. zinat
    March 11, 2014 at 5:41 am

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

  1. October 15, 2014 at 2:49 am
  2. October 17, 2014 at 12:00 am
  3. October 20, 2014 at 9:34 pm

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: