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

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

+20 votes

Best answer

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,465 answers

195,380 comments

100,304 users