CODEWITHSUNDEEP
big-o
ronaldfisher
ronaldfisher

Reputation: 21

Calculating c and n0

I have a quiz in my course where a question goes: ”We have found out that f(n) = 7n^2+3n+8. This means that the function is of O(???) and that c = ??? and n0 = ???”

I know that O(n^2), but I’ve searched every source imaginable in order to find out how to calculate c and n0. In some threads here I reckon that you can pick a value for n0 and then compute c with the given value for n0, but I assume my question requires specific (i.e. correct) values for c and n0 since there seems to be only one right answer in the questions in the quiz.

Upvotes: 1

Views: 3644

Answers (1)

PapaDiHatti
PapaDiHatti

Reputation: 1921

Big-O notation will tell that certain function will not exceed simpler function beyond constant multiple (c) and for large values of n(n0). As we all know that 7n^2+3n +8 is O(n^2) as for large values of n, 3n +8 will be insignificant. So we need to c and n0 such that 

7n^2 + 3n + 8 <= cn^2  for all n >= n0

Dividing by n^2 will give us :

7 + 3/n + 8/n^2 <= c for all n >=  n0

if we choose n0 = 1 we will get

7 + 3 + 8 <= c

so we can set c = 18 and n0 = 1 this can be one of the solutions which means

7n^2 + 3n + 8 <= 18n^2 for all n >= 1

Also I believe there can never be one solution for this answer.

Upvotes: 4

Related Questions