Question

Choose the equivalent Big Oh notation for the functions given below. If there is more than one option, circle the tightest asymptotic bound.

1. function f(n) = 5n - 10 belongs to

a) O(1) b) O(n) c) O(n2) d) O(log n)

2. function f(n) = 4n2 + 4n + 1 belongs to

a) O(1) b) O(n) c) O(n2) d) O(log n)

3. function f(n) = n2 + 100 log n belongs to

a) O(1) b) O(n) c) O(n2) d) O(log n)

Answer 1

f(n) = O(g(n)) if there exists a positive integer n0 and a positive constant c, such that f(n)<=c.g(n) for all n>=n0

1)

f(n) = 5n-10

if g(n) = n

f(n) <100*g(n) for all n>1, f(n) = O(n)

if g(n) = n^2

f(n) <100*g(n)  for all n>1, f(n) = O(n^2)

option b since it is more closer asymptotically

2)

f(n) = 4n^2 + 4n +1

if g(n) = n^2

f(n) <100*g(n) for all n>1, f(n) = O(n^2)

option c

3)  f(n) = n^2 + 100 log n

if g(n) = n^2

f(n) <100*g(n) for all n>1, f(n) = O(n^2)

option c