edited by
380 views
1 votes
1 votes
I am having some problems in calculating time complexities for recurrence relations. In one of the books, I saw two questions-

1.

A(n)

{

if(n<=1) return (n);

else

{ return ( A(n/2)+ A(n/2)+ n);

}

}

The recurrence for this is given as

T(n)= T(n/2)+T(n/2) +c   if n>1

But then another question follows-

Q2.

A(n)

{

if(n<=1) return (n);

else

{ return ( 2*A(n/2)+ 6*A(n/2)+ n^2);

}

}

The recurrence for this is given as

T(n)= T(n/2)+T(n/2) +c   if n>1

I think it should be T(n)= 2T(n/2)+6T(n/2) +n^2

What am I missing here ?
edited by

2 Answers

3 votes
3 votes
No, your answer is incorrect.
Suppose, 2*T(n/2) means calling T(n/2) twice. But in question they have multiply it by 2 not called it twice.
0 votes
0 votes

Q2.

A(n)

{

if(n<=1) return (n);

else

{ return ( 2*A(n/2)+ 6*A(n/2)+ n^2);   ....->>>>     ( a=A(n/2)    ->T(n/2)

                                                                                                b=2*a         ->o(1)

                                                                                               c=A(n/2)   - >T(n/2)                       

                                                                                              d=6*c          -> o(1)

                                                                                              g=b+d+n^2  ->o(1)

                                                                                               return g

                                                                                     recursion relation:-

                                                                                    T(n)  ={ o(1) if n<1

                                                                                                    T(n/2)+T(n/2)+c  if n>1

                                                                                            =2T(n/2)+c

                                                                                            =O(n)

}


}

Related questions

1 votes
1 votes
2 answers
1
0 votes
0 votes
1 answer
2
practicalmetal asked Sep 15, 2023
337 views
Consider the following function:function X(n,r) { if(r==0 or n == r) then return 1; else return (X(n-1,r-1,) + X(n-1,r)); }Find the worst case time complexity of function...
0 votes
0 votes
1 answer
3
Lakshman Bhaiya asked Nov 1, 2018
410 views
Given $T(n)=T(\frac{n}{4})+T(\frac{n}{2})+n^{2},$ then$A)T(n)=\theta(n^{3})$ $B)T(n)=\theta(n^{2}logn)$ $C)T(n)=\theta(n^{2})$ ...
1 votes
1 votes
0 answers
4
NIHAR MUKHIYA asked Jul 15, 2017
427 views
T(n)=T(n/2+2)+nSolution using substitution method