844 views

2 Answers

Best answer
1 votes
1 votes
n+(n-1)+(n-2)+.....+1=$\frac{n \times (n+1)}{2}$
selected by
0 votes
0 votes

We can use Master Theorem for Decreasing function here.

T(n) = a* T(n-b) + n^k

Here, a=1>0 , b=1>0 and k=1

so then, O(n^k+1) i.e O(n^2)   

Related questions

1 votes
1 votes
0 answers
2
srestha asked May 19, 2019
594 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...
1 votes
1 votes
1 answer
3
VikramRB asked Jan 20, 2019
1,005 views
What is the time complexity of the following recurrence relation and step to derive the same$T(n) = T(\sqrt{n}) + log(logn)$
1 votes
1 votes
1 answer
4
Mayankprakash asked Jan 4, 2019
1,265 views
T(n) = T(n/4) + T(3n/4) + nHow to solve these type of problems?Can I solve this using master theorm by considering X = T(3N/4) +N THEN T(N) = T(N/4) +XCAN WE SOLVE LIKE T...