Below is the solution but I have trouble understanding 1 part of the proof by induction part. Why can you just add + 2 to one side and +4 to the other?
We're dealing with the function T(n) = 2n + 2
We want to find a c such that T(n) <= c * f(n) for large n
We have T(n) = 2n + 2 and f(n) = n, so we need 2n + 2 <= c * n
We solve for c and get 2 + 2/n
2/n is undefined at n = 0, so we pick t >= 1. We'll pick t=1, so c=4
Proof by induction:
T(n) <= c * f(n)
(2n + 2) <= (4)(n)
+2 +4 <---- Don't understand
2n + 4 <= 4n + 4
2(n + 1) + 2 <= 4(n + 1)
T(n + 1) <= c * f(n + 1)
Conclusion: 2n + 2 ∈ O(n)
if 2n+2 <= 4n, by adding 2 to the left hand side and 4 to the right hand, you add less to the left hand, so if 2n+2 <= 4n, definetly 2n + 2 <= 4n + 4
So, you basically jumped from 2n+2 <= 4n (which you know to be true from induction hypothesis) to 2n+4 <= 4n+4, since 2<4 and 2n+2<=4n. You later find out that the claim of the induciton hypothesis is also correct for n+1 in the next lines.