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

### Leave a Reply Cancel reply

### Blog Stats

- 77,683 hits

### Algorithms

### Artificial Intelligence

### Blogroll

### Blogs I Like

- Abdul Aleem Khan
- Abdul Azeem Khan
- Adeel Bin Khalid
- Andy Rich
- Ayaz Shahid
- Ayesha Saeed
- Barry Dorrans
- Brad Abrams
- Chris Anderson
- Coding Horror
- Don Box
- Don Syme
- Eric Clippert
- Fahim ul Haq
- Faisal Naveed
- Hammad Hussain
- Harris Moin
- Joel On Software – Joel Spolsky
- Kashif Kaleem
- Mansoor Afzal
- Michal Cierniak
- Miguel De Icaza
- MSN Search Weblog
- Muddassir Shabbir
- Muhammad Abubakar Sultan
- Omer Ashraf Khan
- Omer Shakil
- Paul Grahams
- Raymond Chen
- Rico Mariani
- Scobleizer
- Shaykat Chaudhry
- Somasegar
- Stann Lippman
- Steve Butler
- The Old New Thing
- Usman Ahmad
- WinFS Blogs
- Yun Jinn
- Zubair Nawaz

### Computer Programming

- Coding Horror
- Extensible Application Markup Language – XAML
- Functional Programming Language – F# (Sharp) by Microsoft Research
- Internatiol Olympiad of Informatics
- Microsoft Cฯ (C Omega)
- Microsoft Visual C# (Sharp)
- Microsoft Visual C++ (C Plus Plus)
- Reverse/Re Engineering
- The Perl Programming Language

### Computer Science

### General Knowledge and Information

- Barron’s GRE Vocabulary List – Starting from ‘A’
- Internatiol Olympiad of Informatics
- Joel on Software
- Microsoft Corporation – The Software Giant
- Microsoft MSDN Blogs !
- Microsoft Windows Ideas Live
- MIT’s Open Course Ware
- MSDN – Microsoft’s Developer Network
- Plato and His Dialogues
- Professor Dr. Stephan W. Hawkings
- Space Science and Engineering
- Technical Interview Puzzles
- The Geek Test
- The Google Search Engine related article.
- The MSN Search vs. Google Search !
- The Scientific American
- The String Theory – The Superstring Theory
- The TopCoder – Ultimate Algorithm and Design Component Site
- Ultimate Dictionary Reference
- Wikipedia – The Knowledge World
- WordNet Online Reference

### Mathematics

### Microsoft Related

### Movies

### Nice Links

### Pakistan

### Quantum Computing

### Religion

### Space Science

### Technology

### Universities I have Attended

### Categories

### Recent Posts

### Archives

- June 2010
- August 2009
- July 2009
- May 2009
- April 2009
- March 2009
- February 2009
- January 2009
- October 2008
- September 2008
- August 2008
- July 2008
- April 2008
- March 2008
- January 2008
- December 2007
- September 2007
- July 2007
- March 2007
- January 2007
- December 2006
- November 2006
- October 2006
- September 2006
- August 2006
- July 2006
- June 2006
- May 2006
- April 2006
- March 2006
- February 2006
- December 2005
- November 2005
- September 2005
- August 2005
- May 2005

### Haroon Saeed’s Shared Google Reader

- An error has occurred; the feed is probably down. Try again later.

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..