Recall the definition of big-O: a function f(n) = O(g(n)) if c = R+, n =...

 

Transcribed Image Text:

Recall the definition of big-O: a function f(n) = O(g(n)) if c = R+, n = 1, Vn N1, (n no) f(n) c g(n) For the following pairs of functions, give a formal proof of each claim. a. [4 marks] If f(n) 17n + 6n and g(n) = 2n 4n, then f(n) O(g(n)) = b. [4 marks] If f(n) = 26n log12 n and g(n) : - - 16n3, then f(n) = O(g(n)). 3 ' c. [4 marks] If f(n) = 6n + 3n 84n and g(n) = 16n + 8n - 224, then f(n) O(g(n)). Recall the definition of big-O: a function f(n) = O(g(n)) if c = R+, n = 1, Vn N1, (n no) f(n) c g(n) For the following pairs of functions, give a formal proof of each claim. a. [4 marks] If f(n) 17n + 6n and g(n) = 2n 4n, then f(n) O(g(n)) = b. [4 marks] If f(n) = 26n log12 n and g(n) : - - 16n3, then f(n) = O(g(n)). 3 ' c. [4 marks] If f(n) = 6n + 3n 84n and g(n) = 16n + 8n - 224, then f(n) O(g(n)).