79686779

Date: 2025-07-02 03:17:29
Score: 1
Natty:
Report link

If we track all possibilities, then

first if condition gives us

T(n)=O(n/2)+T(n/2) equivalent to T(n)=O(n)+T(n/2)

second gives us

T(n)=2*O(n/2)+T(n/2) equivalent to T(n)=O(n)+T(n/2)

for the third one

You can easily see that all possibilities will be equivalent to T(n)=O(n)+T(n/4).

From these recursions you can deduce that T(n)=O(n) i.e. the time complexity is linear.

On your merge sort analogy: The array is being broken in a similar way but if you observe carefully we don't operate on each chunk unlike merge sort. Basically at each of logn levels in merge sort we are dealing with all n of them while here with n/(2^i) i.e. decay exponentially.

Reasons:
  • Long answer (-0.5):
  • No code block (0.5):
  • Low reputation (1):
Posted by: Advait Gupta