1,207 views
2 votes
2 votes
int Test(int n) {
    if (n<=0) return 0;
    else {
        int i = random(n-1);
        return Test(i) + Test(n-1-i);
    }
}


Suppose the function $\text{random}()$ takes constant time,  then what is the time complexity of $T(n)$?

3 Answers

Best answer
1 votes
1 votes

This function looks very close to recurrence of QUick Sort . It is recurrence of Quick Sort ! Just instead of partitioning function, we are calling function which has O(1) time. I.e. Constant

So In best case i will be midpoint then !

T(N) = 2(N/2) +c

T(N) = ϴ(lon 2n)

So best case => Ω((lon 2n)

In The worst case, we will alwyas chose i = 0.

Then it will be like

T(N) = T(1) + T(n-1) + c

It will be ϴ(N) in worst case.

 

selected by
1 votes
1 votes

Not sure 

int i = random( n - 1 ); takes constant time to compute as given

Test( i ) +Test( n - 1 - i ) = T(c) +T(n-1-c) 

T(n) = T(n-1) + C = O(n).

0 votes
0 votes
T(n)=C+T(i)+T(n-1-i) .   C= The constant time to generate the random number.

Now in worst case The random number can always generate number 1.So n will be split into 1 and n-1.

So T(i) can execute atmost i times. So T(n)<=C+i*C+(n-1-i)*C=nC =O(n).

Related questions

1 votes
1 votes
2 answers
1
Apeksha asked Aug 6, 2016
738 views
for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) for(l=1;l<=k;l++) printf("gate");
0 votes
0 votes
2 answers
2
radha gogia asked Jul 7, 2018
1,547 views
foo(int n) { for(int i=0 ; i<n ;i++) for(int j=i ; j<=i*i ;j++) if(j%i==0) { for(int k=0;k<j;k++) printf("hii"); } } How to proceed here for analyzing the time complexity...
2 votes
2 votes
1 answer
4
aka 53 asked Nov 22, 2017
958 views
for i < - 1 to n for j < 1 to n/2 X = X + 1(i and j both are incrementing by 1)Outer runs for n times and inner for n/2 So will it be n(n...