What will be the recurrence relation of the following code?
Posted: Wed Jul 13, 2022 7:40 pm
Int sum(int n)
{
If(n==1)
return 1;
else
return n+sum(n-1);
}
a) T(n) = T(n/2) + n
b) T(n) = T(n-1) + n
c) T(n) = T(n-1) + O(1)
d) T(n) = T(n/2) + O(1)
{
If(n==1)
return 1;
else
return n+sum(n-1);
}
a) T(n) = T(n/2) + n
b) T(n) = T(n-1) + n
c) T(n) = T(n-1) + O(1)
d) T(n) = T(n/2) + O(1)