Question

show the following is a O(n^2) by supplying answers to the three steps below.

f(n)=9n^2+4

1 setup the problem
2 isolate constant c
3 determine values for k and c that make this inequality bold

Answer 1

Question:

Show the following is a O(n²) by supplying answers to the three steps below.

f(n)=9n²+4

1 setup the problem
2 isolate constant c
3 determine values for k and c that make this inequality bold

Answer:

Let f and g be functions from positive numbers to positive numbers. f(n) is O(g(n)) if there are positive constants C and k such that:

f(n) ≤ C.g(n) whenever n > k

Taking value of k = 1.

Assuming n >1,

Choose C = 13

Thus, 9n²+4 is O(n²) because 9n²+4 < 13n² whenever n>1.

Consequently, we can take C = 13 and k = 1 as witnesses to show that f (n) is O(n²).