CODEWITHSUNDEEP
time-complexitycomplexity-theory
Yazgan
Yazgan

Reputation: 151

How to find the time complexity of the following code?

Could you explain how to find time complexity of the folowing code? Any help appreciated.

int boo(n) {
    if (n > 0)
    {
         return 1 + boo(n/2) + boo(n/2);
    }
    else 
    {
         return 0;
    }
}

Upvotes: 4

Views: 165

Answers (1)

libik
libik

Reputation: 23029

enter image description here

Sometimes it is good to write it down. When you start, it sum 1 + boo(n/2) + boo(n/2), which is on the second line.

And each of that n/2 is run also

etc. etc.

So at the end, while the number of calls is growing exponencially, the number of repetions is only logharitmic, which at the end remove each other and you got O(N).

PS : It is enough to count down the last line, the whole tree has always only once time more nodes (minus one), which in complexity theory is neglible (you dont care about constants, which multiplicating by two is)

Upvotes: 1

Related Questions