What is the running time complexity of the given function?

Posted on 2011-05-02
Medium Priority
Last Modified: 2012-08-14
The following question is one of the questions from an in-class homework assignment page that I don't believe we ever went over:

What is the running time complexity of the given function?
          int mystry(int n) {
                if  ( n == 0 ) return 0 ;
                return 1+ mystry(n/2) ;

Open in new window

Could you please also give me a quick explanation of how this type of proplem is solved?
Question by:Eindoofus
LVL 27

Expert Comment

ID: 35505725
You have to simulate the function processing by hand.

How many times do you execute the loop if n=8, 16, ... for example?
LVL 32

Accepted Solution

phoffric earned 2000 total points
ID: 35505738
if n = 8
return 1+ mystry(4)
                return 1 + mystry(2)
                                 return 1 + mystry(1)
                                                  return 1 + mystry(0)
                                                                   return 0
1+4 steps

if n = 16
return 1+ mystry(8)
1 + 5 steps
if n = 32
1 + 6 steps

16 = 2^4
32 = 2^5

log(base 2)(32)=5

So what is the complexity?

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Dependencies in Software Design In software development, the idea of dependencies (http://en.wikipedia.org/wiki/Coupling_%28computer_programming%29) is an issue of some importance. This article seeks to explain what dependencies are and where they …
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
Suggested Courses
Course of the Month16 days, 4 hours left to enroll

850 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question