0

I have following method

int function(int n) {
    if(n<20) {
        return 19;
    }
    return 20 + function(n/2) + function(n/2);
}

I believe that the runtime complexity with function(n/2) is O(log(n)). But I am confused about this. Can anyone explain the runtime complexity for this method. I would really appreciate your effort.

Thanks

Sai Kishore
  • 326
  • 1
  • 7
  • 16
Nawaraj Sharma
  • 33
  • 4
  • 1
    Why don't you return `return 20+2*function(n/2)`? – clinomaniac Apr 03 '18 at 05:51
  • @clinomaniac I have no problem with that. But what happens to my runtime complexity? – Nawaraj Sharma Apr 03 '18 at 05:53
  • 4
    Technically it stays the same. Still will be `O(log n)` since you are reducing the problem by half every time. `O(2 log n)` = `O(log n)` – clinomaniac Apr 03 '18 at 05:53
  • Remember constants get dropped out of big O complexities. See https://stackoverflow.com/questions/22188851/why-is-constant-always-dropped-from-big-o-analysis So if you do `function(n/2)` 2, 4 or 10 times as long as its constant it wont matter for big O (at its current location) – ug_ Apr 03 '18 at 05:58
  • Oh.. I didnt realise that. I was just focusing that when it is called twice from the same method it would make it O(2^n) and eventually it would change O(log n) – Nawaraj Sharma Apr 03 '18 at 05:58
  • @ug_ Thanks for the link. It really helped me understand that concept ;) – Nawaraj Sharma Apr 03 '18 at 06:00

1 Answers1

0

It will be o(2^(log n)) = O(log n). Consider an example of taking n = 64. if the base case was not 20 which we can think of as constant it will take 64 lines of execution at each step. Example- f(64) = 20+f(32)+f(32) = 1 line and for calculation f(32)= 20+f(16)+f(16) there are 2 f(32) so at here it will be 2 lines and at every downstep it will multiply current no. of current lines with 2 and so on.

Siddhant
  • 41
  • 5