Using induction to prove a big O notation
In essence, your proof is correct. A more general solution that you can use for recursive algorithms is this.

The way to solve this is to create a function T(n) that measures the runtime of the function and figure out the big O notation for it.

To solve a problem of size n, I must solve a problem of size n - 1. Then I must perform constant time arithmetic to get the answer. Thus :

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


Prove T(n) is O(n) ie by definition

T(n) &lt;= cn for all n &gt;= n0


Assume:

T(n - 1) &lt;= c(n - 1)


then

T(n) = T(n - 1) + O(1)
T(n) &lt;= c(n - 1) + d
T(n) &lt;= cn + d - c
T(n) &lt;= cn for c &gt;= d


use T(1) as a base case to complete the proof, giving you n0 = 1