Question $1$ SET A

$[6$ Marks$]$

Find the recurrence relation for the given pseudo code and calculate its time complexity using

the substitution method.

Verify the time complexity obtained with the substitution method using the recursion tree

method.

ALGORITHM BinRec$(n)$

$//$Input: A positive decimal integer $n$

$//$Output: The number of binary digits in $n\text{'}$s binary representation

if $n=1$ return $1$

else return BinRec$({|}_{{?}_{?}}\frac{n}{2_{{?}_{?}}}|)+1$

Question $1$ SET B

$[6$ Marks$]$

Find the recurrence relation for the given pseudo code and calculate its time complexity using

the substitution method.

Verify the time complexity obtained with the substitution method using the recursion tree

method.

IALGORITHM $S(n)$

$//$Input: A positive integer $n$

$//$Output: The sum of the first $n$ cubes

if $n=1$ return $1$

else return $S_{{?}_{?}}(n-1)+n**n**n$