Solving the recurrence relation $T(n)=T(n−1)+O(n)$ for $n > 1$, $T(1)=1$.

Question

I want to solve the recurrence relation $T(n)=T(n−1)+O(n)$ for $n > 1$, $T(1)=1$.

what is $O(n)$? is $O(n)$ equals to constant or what?

Can anyone help me solve this?

Answer 1

$O(n)$ is some function $g$ that is asymptotically upper bound by the function $f(n) = n$. The definition of the Big-$O$ notation says $g(n) = O(f(n))$ if there exists some constant $c \in \mathbb{R}$ such that there exists an $n' \in \mathbb{N}$ with $g(n) \leq c f(n)$ for all $n > n'$.

Let's first develop some intuition for the recurrence by substituting $T(n-1)$ with $T(n-2) + O(n)$ the right hand side. This is valid because we are just replacing $T(n-1)$ with the image of $n-1$ under $T$.

$T(n) = T(n-1) + O(n) = (T(n-2) + O(n)) + O(n)$

The goal is to express $T(n)$ in terms of $T(1)$. Now let's substitute $T(n-2)$ to get an answer in terms of $T(n-3)$.

$T(n) = ((T(n-3) + O(n)) + O(n)) + O(n)$

We see a pattern emerging. Each time we substitute $T(n-i)$ we pick up an additional $O(n)$. In general we have $T(n) = T(n-i-1) + \sum_{k=1}^i O(n)$. Since $1 = n - (n - 1)$ we set $i$ equal to $n - 1$ in our equation.

$T(n) = T(1) + \sum_{k=1}^{n-1} O(n) = 1 + \sum_{k=1}^{n-1} O(n) = O(n^2)$

We end up with the solution $O(n^2)$ since we are summing up $O(n)$ terms equal to $O(n)$.

Answer 2

$\mathcal{O}(n)$ denotes Big-O notation, that is it is linear. You can substitute $\mathcal{O}(n)$ with $n$ to solve the recurrence.