Big-O proof: Master Theorem

← Courses›Interview PrepModule 4 · Dynamic Programming & Heap›Big-O proof: Master Theorempredict63 / 100

Task

📝 **Question:** What's the asymptotic complexity of T(n) = 4T(n/2) + O(n²)? Type the answer in the form O(n^k) or O(n^k log n).

📋 Pick the right answer.

💡 **Hint:** Re-read the theory above if unsure.

Keep going

🎯quiz

Behavioral: a project that failed (STAR)

🎯writeFREE

Two pointers: pair sum

🎯write

Two pointers: palindrome check

🤖predictFREE

Prerequisites — what you should know before this track

⚡predictFREE

Prerequisites — what you should know before this track

🔮 Predict the output

Read the code carefully

# Recurrence: T(n) = 4·T(n/2) + O(n²)
# Master Theorem: a=4, b=2, d=2 → a/b^d = 4/4 = 1 → Case 2
# Answer: ?
print('O(n^2 log n)')

What will the program print? Write here:

Keep going

💬 Discussion