Applied Gate Test Series

Question

Consider the function given below ?

Assume T(0) = 0

int fun( int n )
{
    if ( n <= 0 ) return 0;
    int i = random( n - 1 );
    return fun(i) + fun(n - i - 1);
}

random(n) returns an integer in the range [0, n] in constant time

What is the time complexity of the above function?

1. $\Theta (n^{2})$  
2. $\Theta (n)$
3. $\Theta (n\log n)$
4. None

Answer 1

Recurrence relation for this is

$T\left ( n \right )=\left\{\begin{array}  {lcl} T(n -1)+T(1)+1 & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\right. $

In the worst case, the random function gives $0 \text { or } n$ in each call.

So, time complexity of this recurrence is $T(n) = \Theta (n)$

Comments

@Yaman , what is the meaning of this statement “In the worst case, the random function gives 1 in each call.”

---

@Yaman , what is the meaning of this statement “In the worst case, the random function gives 1 in each call.”

 Actually, the partition of function depends on a random function

If random function gives 0 or n then T(n) = T(n-1) + 1

My mistake is I miss out on last fun(i) + fun(n - i - 1); subtraction.

Correct it.

---

now fine.