Solving Recurrence using Master Method

Question

I'm trying to solve a recurrence relation to find out the complexity of an algorithm I wrote. This is the equation..

T(n) = T(n-1) + Θ(n)

And I found out the answer to O(n2), but I'm not sure if I did it right. Can someone please confirm?

Update: What if the equation is T(n) = T(n-1)+Θ(nlogn)? Will it still be O(n2)?

Answer 1

It is O(N)+O(N-1)+...+O(1) = O(N*(N+1)/2). So yes, the total complexity is quadratic.

Answer 2

Yes, you guess it right.

However, the form of the recurrence doesn't fit with Master method. Since you have guessed the bound correctly, substitution method is more suitable here.

Now your job is finding two constants c and n0 to prove that:

T(n) <= c*(n^2) forall n >= n0