Time complexity of recursive function with input halved

user_1086223 0
Viewed 219

For those Big O experts out there... I'm trying to deduce the time complexity of a function with two recursive calls, where the input is halved each time:

function myFunc(n) {
  if (n > 1) {
    let something = 0

    for (let i=0; i < n; i++) {
      // Do some linear stuff in here
    }

    myFunc(n/2)
    myFunc(n/2)
  }

  return something;
}

I'm unsure how, exactly, the halving effects the analysis. Any help super appreciated!

big-o time-complexity
1 Answers

The first step in the analysis of a recursive function would be to write down the recurrence relation. In this case you have:

T(n) = 2T(n/2) + O(n)

This is one of the most common forms of recurrence relations, so we can immediately state the solution without any further calculations:

T(n) = O(n log n)

It's easy to prove this result by induction. See e.g. here.

user_6899230
Related