Algorithms and Data Structures · Middle · Question 64 of 75

What is the complexity of this function?

function f(n) {
  if (n <= 1) return 1;
  return f(n / 2) + f(n / 2);
}

Explanation

Each call makes two calls on half the input, so the call tree has 1 + 2 + 4 + ... + n ≈ 2n nodes with O(1) work each. If it made one call, f(n / 2) alone, it would be O(log n).

Further reading

Problem with a question

Algorithms and Data Structures · Middle · question 64

Test yourself

Take the Algorithms and Data Structures · Middle quiz: questions and options are shuffled, and you get a review of your mistakes at the end.

Take this quiz