🎴 Flashcard Mode
Algorithm Time Complexity Analysis
Card1 / 25
Mastered0
Review0
QuestionClick to flip
Directions: Find the time complexities of the following question.
T(n)=3T(n/4)+c(n2)
AnswerClick to flip back
A
O(n2)
💡 Explanation:
Using Master Theorem: a=3, b=4, f(n)=n^2. Since n^(log_4(3)) ≈ n^0.79 < n^2, we're in Case 3 where f(n) dominates. Therefore T(n) = O(n^2). The recursive calls at each level contribute polynomial work, but the n^2 term at the root determines overall complexity.