The Gateway to Computer Science Excellence
+11 votes
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$.

in Algorithms by Veteran (52.2k points)
edited by | 658 views

1 Answer

+20 votes
Best answer
$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

@Ayush Upadhyaya

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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,465 answers
195,380 comments
100,304 users