Question

Problem 1 [15pts. Recall how we solved recurrence relation to find the Big-O (first you need to find closed-form formula). Use same method (expand-guess-verify) to figure out Big-O of this relation. (You can skip last step "verify", which is usually done by math induction). T (1) 1 T(n) T(n-1)+5

Answer 1

Considering our base condition as:

(i) T(1) = 1

The time equation given in question can be considered as follows:

(ii) T(n) = T(n-1) + C (where C = 5 and n > 1)

Now let's solve this recurrence relation and try to express it in terms of base condition.

Consider the equation (i), by replacing n by n - 1 we can say that,

(iii) T(n-1) = T(n-1-1) + C = T(n - 2) + C

Using equation (iii) in (ii) we can say that,

(iv) T(n) = T(n-2) + C + C = T(n-2) + 2C

Following the same way we can say that

T(n) = T(n-2) + 2C = T(n-3) + 3C = T(n-4) + 4C

Hence,

T(n) = T(n-K) + KC

To express in term of base condition T(1) = 1,

-> T(n - K) = T(1)

-> n - K = 1

-> K = n - 1

So T(n) can be written as,

-> T(n) = T(n-K) + KC = T(n-(n-1)) + (n-1)C

-> T(n) = T(1) + nC - C

-> T(n) = nC - C + 1 (as per base conditions)

As we can see T(n) is directly proportional to n, hence,

T(n) = O(n)