Question

1.)Prove that f(n) = O(g(n)), given: F(n) = 2n + 10; g(n) = n

2.)Show that 5n² – 15n + 100 is Θ(n² )

3.)Is 5n² O(n)?

Answer 1

1)
f(n) = O(g(n)) means there are positive constants c and n0, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0

2n + 10 = O(n)
=>  2n + 10 <= c(n)
Let's assume c = 3
=>  2n + 10 <= c(n)
=>  2n + 10 <= 3n
=>  10 <= n
it's true for all n >= 10

so, 2n + 10 = O(n)

2)
f(n) = Θ (g(n)) means there are positive constants c1, c2, and k, such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0. The values of c1, c2, and n0 must be fixed for the function f and must not depend on n.

5n^2 – 15n + 100 is Θ(n^2)

=>  c1(n^2) <= 5n^2 – 15n + 100 <= c2(n^2)
Let's assume c1 = 1 and c2 = 5
=>  c1(n^2) <= 5n^2 – 15n + 100 <= c2(n^2)
=>  1(n^2) <= 5n^2 – 15n + 100 <= 5(n^2)
=>  n^2 <= 5n^2 – 15n + 100 <= 5n^2
=>  n^2 <= 5n^2 – 15n + 100 and 5n^2 – 15n + 100 <= 5n^2
=>  0 <= 4n^2 – 15n + 100 and 100 <= 15n
These are true for all n >= 1

so, 5n^2 – 15n + 100 is Θ(n^2) given c1 = 1, c2 = 5 and n0 = 1

3)
No, 5n^2 is not O(n)