Gupta ji created his new algorithm and the recurrence for his algorithm came out to be: -...
Palo Alto Networks technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Gupta ji created his new algorithm and the recurrence for his algorithm came out to be:
- T(n) = T(n/4) + T(n/2) + cn^2
- T(1) = c
- T(0) = 0
What is the value of following recurrence where c is a positive constant?
Select any one of the following
Show answer & explanation
Using the Master Theorem or Akra-Bazzi recurrence tree, the work at each level is dominated by the root cn^2 since (1/4)^2 + (1/2)^2 = 5/16 < 1. The sum of geometric series converges to O(n^2).
Step-by-step Derivation:
Step 1: Write down recurrence: T(n) = T(n/4) + T(n/2) + cn^2.
Step 2: Level 0 cost = cn^2. Level 1 cost = c(n/4)^2 + c(n/2)^2 = cn^2(1/16 + 1/4) = (5/16)cn^2.
Step 3: Since the common ratio r = 5/16 < 1, the total cost forms a decreasing geometric series: T(n) = cn^2 * sum_{k=0}^inf (5/16)^k = (16/11)cn^2 = O(n^2).