What is the running time complexity of the given function?

Posted on 2011-05-02
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 26

    Expert Comment

    You have to simulate the function processing by hand.

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

    Accepted Solution

    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?

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Highfive + Dolby Voice = No More Audio Complaints!

    Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

    Suggested Solutions

    The Fluent Interface Design Pattern You can use the Fluent Interface ( design pattern to make your PHP code easier to read and maintain.  "Fluent Interface" is an object-oriented design pattern that r…
    Introduction Many of the most common information processing tasks require sorting data sets.  For example, you may want to find the largest or smallest value in a collection.  Or you may want to order the data set in numeric or alphabetical order. …
    Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…
    Viewers will learn about if statements in Java and their use The if statement: The condition required to create an if statement: Variations of if statements: An example using if statements:

    760 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

    Need Help in Real-Time?

    Connect with top rated Experts

    8 Experts available now in Live!

    Get 1:1 Help Now