recategorized by
2,696 views
15 votes
15 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$.

recategorized by

1 Answer

Best answer
29 votes
29 votes
$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}$
edited by

Related questions

30 votes
30 votes
4 answers
2
Kathleen asked Sep 29, 2014
4,524 views
Let $\left(\{ p,q \},*\right)$ be a semigroup where $p*p=q$. Show that:$p*q=q*p$ and$q*q=q$