304 views

1 Answer

Best answer
0 votes
0 votes
T(n)=T(n-1)+n;

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

T(n-2)=T(n-3)+n-2;

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

T(n)=T(n-3)+n-2+n-1+n;

T(n)=T(n-k) +n*k -(1+2+3....k);

now at k=n we get T(0)=1;

so T(n)=T(0)+n*n- (1+2+3....n);

we get n^2-n(n+1)/2

T(n)=O(n^2)
selected by

Related questions

0 votes
0 votes
1 answer
1
Mayankprakash asked Oct 31, 2018
846 views
I want to learn to find time complexity of the recurrence relation of an algorithm.Please suggest some good links or any gatetoverflow imp questions links to look as exam...
0 votes
0 votes
1 answer
2
1 votes
1 votes
1 answer
3
1 votes
1 votes
0 answers
4
srestha asked May 19, 2019
596 views
Let $A(n)$ denotes the number of $n$ bit binary strings which have no pair of consecutive $1’s.$ what will be recurrence relation for it and what will be it’s Time Co...