Skip to main content
🔒 Preview mode. The first 15 Foundations lessons are free; this one is Pro. Start a 7-day trial to unlock the editor, AI hints and the rest of the curriculum. Card required, cancel any time in Dashboard.Start 7-day trial →
← CoursesInterview PrepModule 4 · Dynamic Programming & Heap · RecapBig-O proof: Master Theorempredict66 / 104
+75 XP
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.
Predict the output

Read the code carefully

# Apply the Master Theorem to:
#
#     T(n) = 4·T(n/2) + O(n²)
#
# Extract:
#     a = ?    # number of subproblems
#     b = ?    # shrink factor
#     d = ?    # exponent of the combine cost
#
# Compare a / b^d to 1 and pick the matching case (1, 2, or 3).
#
# What does T(n) resolve to? (form: 'O(n^k)' or 'O(n^k log n)')
# Type your prediction.

What will the program print? Write here:

💬 Discussion

Be the first to ask a question or share a tip.
Sign in to join the discussion. Reading is free.
Loading discussion…