What will be base case for this recurrence?

Can we say an=an-1+1 with base case as a1 =0??

The Gateway to Computer Science Excellence

+12 votes

Consider the recursive algorithm given below:

procedure bubblesort (n); var i,j: index; temp : item; begin for i:=1 to n-1 do if A[i] > A[i+1] then begin temp := A[i]; A[i] := A[i+1]; A[i+1] := temp; end; bubblesort (n-1) end

Let $a_n$ be the number of times the ‘if…then…’ statement gets executed when the algorithm is run with value $n$. Set up the recurrence relation by defining $a_n$ in terms of $a_{n-1}$. Solve for $a_n$.

+21 votes

Best answer

+5

Base case should be 1 as when there is only 1 element,no sorting needs to be done.

T(1)=1.

Recurrence must be

$T_n=T_{n-1}+n-1$

$T_n=T_{n-2}+(n-1)+(n-2)$..

After $k^{th}$ iterations

$T_n=T_{n-k}+(n-1)+(n-2)+(n-3)+(n-4)+.....+(n-k)$

$k^{th}$ iteration would be last iteration when n-k=1 (Base case T(1)=1) so k=n-1.

$T_n=T(1)+(n-1)+(n-2)+(n-3)+....+1=1+\frac{n(n-1)}{2}$

T(1)=1.

Recurrence must be

$T_n=T_{n-1}+n-1$

$T_n=T_{n-2}+(n-1)+(n-2)$..

After $k^{th}$ iterations

$T_n=T_{n-k}+(n-1)+(n-2)+(n-3)+(n-4)+.....+(n-k)$

$k^{th}$ iteration would be last iteration when n-k=1 (Base case T(1)=1) so k=n-1.

$T_n=T(1)+(n-1)+(n-2)+(n-3)+....+1=1+\frac{n(n-1)}{2}$

52,345 questions

60,489 answers

201,830 comments

95,296 users