658 views

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$.

edited | 658 views

$a_n= a_{n-1} + n-1$ ($n-1$ comparisons for $n$ numbers)

$a_n= a_{n-2} + (n-2)+(n-1)$

$a_n= a_{n-3} + (n-3)+(n-2)+(n-1)$
.
.
.

$a_n= a_{n-n} + (n-n) + (n-(n-1)) + .... + (n-3)+(n-2)+(n-1)$

$a_n= 0 + 1 + 2 + ....+ (n-3) + (n-2) + (n-1)$

which given $a_n= \frac{(n-1) \times (n)}{2}$
by Boss (33.8k points)
edited by
0

What will be base case for this recurrence?

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

+4
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}$
0

T(n) = T(n-1) + n-1

can you tell me how u got this n-1 by seeing the code. ?

+3
The for loop runs for n-1 times plus a recursive call to bubblesort with problem size of n-1 give

$a_n=a_{n-1}+n-1$
0
ya, i missed that. tx