The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+8 votes
501 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$.

asked in Algorithms by Veteran (59.7k points)
edited by | 501 views

1 Answer

+19 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}$
answered by Boss (34.1k 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??

+1
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. ?

+1
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

44,510 questions
49,966 answers
165,814 comments
65,915 users