Results 1 to 4 of 4
Like Tree2Thanks
  • 1 Post By emakarov
  • 1 Post By emakarov

Math Help - big O witnesses

  1. #1
    Newbie
    Joined
    Aug 2013
    From
    pakistan
    Posts
    22

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    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?
    Thanks from annie12
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2013
    From
    pakistan
    Posts
    22

    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    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.
    Thanks from annie12
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. False witnesses
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 21st 2009, 08:14 PM
  2. Witnesses for Big O
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: March 11th 2006, 05:57 AM

Search Tags


/mathhelpforum @mathhelpforum