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)?
It is O(N)+O(N-1)+...+O(1) = O(N*(N+1)/2). So yes, the total complexity is quadratic.