Skip to main content
Share Your Experience: Take the 2024 Developer Survey

New answers tagged

1 vote

Big O notation of T(n) = T(n/2) + O(log n) using master theorem?

You check very carefully whether you can apply the master theorem in this case at all. Or you just note that T(n) is just the sum of O(log 2^k) for 1 <= k < log n, which equals O(log^2 n). In ...
gnasher729's user avatar
  • 30.4k
2 votes
Accepted

Solving recurrence relation $T(n) = \max\{T(k)+T(n−k)+O(\min\{k, n-k\})\}$

It gives $T(n) = O(n \log n)$. Let's prove by induction that $T(n) \le Cn \log n$, for some big enough $C \in \mathbb{R}$: The induction hypothesis is that $T(n) \le C n \log n$. Now take $T(1) = 0$ ...
izanbf1803's user avatar

Top 50 recent answers are included