Question

1. Let f(n)=3 n²+4 n+3+log (n). Use the definition of big O to show f=O(2ⁿ) by finding witnesses C and k that satisfy the inequality in the definition.

Answer 1

To show that f(n)=3n²+4n+3+log(n) is O(2ⁿ), we need to find witnesses C and k that satisfy the inequality: f(n) ≤ C*2ⁿ for all n ≥ k. By choosing C = 1 and k = 0, we can simplify f(n) and show that for all n ≥ 0, f(n) is less than or equal to a polynomial function of degree 2, which is dominated by the exponential growth of 2ⁿ.

Step-by-step explanation:

To show that f(n)=3n²+4n+3+log(n) is O(2ⁿ), we need to find witnesses C and k that satisfy the inequality: f(n) ≤ C*2ⁿ for all n ≥ k. Let's find the witnesses:

Since 2ⁿ grows exponentially, we can assume that C*2ⁿ will eventually dominate f(n). Let's set C = 1 and choose k = 0.

For all n ≥ 0, we can simplify f(n) as follows:

f(n) = 3n² + 4n + 3 + log(n)

≤ 3n² + 4n + 3 + log(2ⁿ), since log(n) ≤ log(2ⁿ) when n ≥ 0

≤ 3n² + 4n + 3 + n, since log(2ⁿ) = n

≤ 4n² + 4n + 3

≤ 4n (2n+1) + 3

2n and 2n+1 > 1

≤ 8n² + 4n + 3

This shows that for all n ≥ 0, f(n) ≤ 8n² + 4n + 3, which is a polynomial function of degree 2. Since f(n) is polynomial and C*2ⁿ grows exponentially, we have shown that f(n) is O(2ⁿ).