Let T(n) be defined for powers of 2 by T(1) = 1 and, for n > 1, T(n) = 2T(n/2)…

Concept

For a divide-and-conquer recurrence T(n) = aT(n/b) + f(n), the Master Theorem compares f(n) with n(logb a). If f(n) is polynomially smaller, the leaves dominate and T(n) = Θ(n(logb a)).

A recursion-tree cross-check adds the work at every level and the cost of all leaves.

Application

1. Here a = 2 and b = 2, so n(log₂ 2) = n. The non-recursive term √n is O(n(1−1/2)), which is polynomially smaller than n.

2. At recursion level i there are 2i subproblems of size n/2i. Their total non-recursive work is 2i × √(n/2i) = √n × (√2)i.

3. The depth is k = log2 n. The leaf cost is 2k × T(1) = n, and the internal-level sum √n × Σi=0k−1 (√2)i is Θ(n).

Cross-check

Master Theorem case 1 gives T(n) = Θ(n). The recursion tree independently gives Θ(n) leaf cost plus Θ(n) internal work, confirming the same result.

Therefore T(n) = Θ(n). Among the listed Big-O choices, O(n) is the tightest upper bound; O(n²) is also an upper bound but is asymptotically looser.