Solved

# What is the running time complexity of the given function?

Posted on 2011-05-02
Medium Priority
383 Views
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) ;
}
``````

Could you please also give me a quick explanation of how this type of proplem is solved?
0
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?
0

LVL 32

Accepted Solution

phoffric earned 2000 total points
ID: 35505738
if n = 8
mystry(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?
0

## Featured Post

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