recategorized by
5,183 views

4 Answers

Best answer
36 votes
36 votes
$T(n) = T(n-1)+n$
           $=T(n-2)+(n-1)+n$
           $=T(n-3)+(n-2)+(n-1)+n$
           .
           .
           .
           $=T(n-k)+\left[(n-k+1)+ (n-k+2)+\ldots+(n-1) + n\right]$   

Recurrence stops at,

$n-k=1$
$k=n-1$

$\therefore T(n) = T(1)+\left[2+3+\ldots+n\right]
\\= 1+ 2+3+\ldots + n
\\= \frac{n(n+1)}{2}$

PS: Unless explicitly asked for asymptotic bound, we should always try to get the exact answer.
edited by
14 votes
14 votes

by using master theorm

6 votes
6 votes

Here they have asked solution in terms of n and not in terms of “big-oh”

0 votes
0 votes
I think iteration method works here pretty well(Backwards substitution)

T(1) = 1
T(2) = 2 +T(1)  = 2 + 1
T(3) = 3 + T(2)  = 3 + 2 + 1
wow a pattern right
I claim
T(n) = n + n-1 + ... + 4 + 3  +2 + 1 = n(n+1)/2

Related questions

23 votes
23 votes
9 answers
3
makhdoom ghaya asked Nov 14, 2016
5,015 views
Show that the conclusion $(r \to q)$ follows from the premises$:p, (p \to q) \vee (p \wedge (r \to q))$
22 votes
22 votes
6 answers
4
makhdoom ghaya asked Nov 14, 2016
5,343 views
Give a regular expression over the alphabet $\{0, 1\}$ to denote the set of proper non-null substrings of the string $0110$.