Question

Example 3: Show -n2 + 2n + 2 € O(n?). Solution: We need to find constants ceR+ and no E Z+, such that for all n > no, In? + 2n+2 5C.n?. Pick c = i +2+2 = 17/4, then we need to find no such that for all n > no, in+2n+25 77. n?. By similar reasoning given above, for all n > 1, n 1 1 17 n² + 2n+2 <=n² + 2n² + 2n so choose no = 1. Therefore, by the definition of Big-Oh, in2 + 2n + 2 is O(n^). 2 -n2. 4 4 4 - Prove r(n) = 1+2+4+8+ 16 +...+2" is O(2").

Answer 1

To prove that r(n) = 1+2+4+8+16+...+2^n is O(2^n), we need to find constants c and no such that for all n > no, r(n) <= c(2^n).

First, let's express r(n) as a geometric series:

r(n) = 1 + 2 + 4 + 8 + ... + 2^n = (1 - 2^(n+1)) / (1 - 2)

Simplifying this expression, we get:

r(n) = 2^(n+1) - 1

To prove that r(n) is O(2^n), we need to show that there exist constants c and no such that for all n > no, r(n) <= c(2^n). Let's choose c = 2 and no = 1. Then:

r(n) = 2^(n+1) - 1 <= 2^(n+1) (since -1 is negative)

And for n > 1:

2^(n+1) <= 2^n * 2 = 2^(n+1)

Therefore, for all n > no = 1:

r(n) <= 2^(n+1) <= c(2^n)

Hence, r(n) is O(2^n), and we have proven it.

Step-by-step explanation: