Reputation: 23

Deriving a Big O notation by Algorithm time-complexity analysis

int m(int i)                                                                                     
{
if (i==1)                                                                                     
    return i;                                                                                 
else                                                                                            
    return m(i-1) + m(i-1)；                                                     
        }

I did the following: Lines 3 and 4 counts for 1 each. I have no idea for calculating the number of times line 5 & 6 will be checked. Since it is recurrsive how can I to derive the big O notation?

Upvotes: 0

Answers (2)

Tim Biegeleisen

Reputation: 520968

You may understand this best perhaps by just writing out on a piece of paper what the function calls look like for some small input, say i == 3:

            m(3)
       /           \
    m(2)           m(2)
  /      \       /      \
m(1)     m(1)  m(1)     m(1)

It should be clear that at each level, the number of function calls doubles. This is exponential behavior, and so the complexity is roughly O(2^n), where n is the input value.

Upvotes: 3