# big O witnesses

• Oct 5th 2013, 07:53 AM
annie12
big O witnesses
Q)to establish the big O relationship ,find witnesses C and K for the function
f(n)=13n^3 +42n^2+2nlogn +4n
solution:
i try to solve it as
when nlogn>n and n^2>nlogn and n^3>n^2
13n^3 +42n^2+2nlogn +4n<=13n^3 +42n^2 +2nlogn +4nlogn<=13n^3+42n^3+2n^3+4n^3<=61n^3
so witnesses are C=61 k=nlogn
big O(n^3)
................
i dont get the idea how to get different witnesses ,i try to understand through text but it a really a difficult topic to understand ,i do it as much as i understand .please explain me if i do it wrong or right
• Oct 5th 2013, 08:40 AM
emakarov
Re: big O witnesses
Yes, you can take C = 61. However, k = n log(n) is incorrect because k has to be a concrete number that does not depend on n, just like C. You can pick k as the smallest number such that for n ≥ k all of the following inequalities, which you used, hold:

n ≤ n^3
n log(n) ≤ n^3
n^2 ≤ n^3

Can you find a k like this?
• Oct 6th 2013, 12:20 AM
annie12
Re: big O witnesses
so can we take k=0 or k=2 0r k=13 or k=42 or k=4 in this question
• Oct 6th 2013, 06:45 AM
emakarov
Re: big O witnesses
Concerning k = 0, it depends on the definition of big-O, whether it says "for all n ≥ k" or "for all n > k". In the first case, the problem is that n log(n) ≤ n^3 does not hold for n = 0 since log(0) is undefined. All other values of k work.