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 ?