Results 1 to 8 of 8

Thread: Proving Big O using Mathematics/Functions

  1. #1
    Newbie
    Joined
    Nov 2017
    From
    LA, USA
    Posts
    4

    Proving Big O using Mathematics/Functions

    Could someone please explain how Big O can be transferred from code and its notation, into functions of f(x) and g(x), etc., and shown using Mathematics and logarithms?
    It's a new topic for me, so I'm quite lost and would appreciate some help!

    Additionally, I'm looking at Bubble Sort and Quick Sort, however I only know an example of coding for both. I do not know how to explain them in terms of the mathematical perspective. I want to start by analyzing their examples, and then (using diagrams) talk about their difference. But I'm entirely lost!

    Please help! (Step-by-step explanations are really helpful, since I'm a relatively slow learner and don't 'see' things immediately.)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,415
    Thanks
    2889

    Re: Proving Big O using Mathematics/Functions

    I'm not sure I understand what you are talking about. My idea of "Big O" is that f(x) is said to be in "O(g(x))" or f= O(g(x)) if and only if $\lim_{x\to\infty}\frac{f(x)}{g(x)}$ is a finite, non-zero number. I don't know what that has to do with "code" or "logarithms". Do you have an example problem?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2017
    From
    LA, USA
    Posts
    4

    Re: Proving Big O using Mathematics/Functions

    How about proving that the running time T(n) = n + 20n +1 is O(n^4)?
    Could you maybe explain the 'average'/expected case in Quicksort that is C(n) = n+ C(k-1) + C(n-k), C(0) = C(1) = 0 ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,971
    Thanks
    1141

    Re: Proving Big O using Mathematics/Functions

    Quote Originally Posted by kazuki00 View Post
    How about proving that the running time T(n) = n + 20n +1 is O(n^4)?
    Could you maybe explain the 'average'/expected case in Quicksort that is C(n) = n+ C(k-1) + C(n-k), C(0) = C(1) = 0 ?
    HallsofIvy was giving the definition of small o notation, I believe. I think the big O notation is that the limit evaluates to zero (I could be wrong, as I have not actually studied this material, and am using context clues to make assumptions).
    Check if the following limit is zero:
    \displaystyle \lim_{n \to \infty} \dfrac{T(n)}{n^4} (Hint: it is zero)

    I have no idea what you are asking for the second question. What is k?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,971
    Thanks
    1141

    Re: Proving Big O using Mathematics/Functions

    Quote Originally Posted by SlipEternal View Post
    HallsofIvy was giving the definition of small o notation, I believe. I think the big O notation is that the limit evaluates to zero (I could be wrong, as I have not actually studied this material, and am using context clues to make assumptions).
    Check if the following limit is zero:
    \displaystyle \lim_{n \to \infty} \dfrac{T(n)}{n^4} (Hint: it is zero)

    I have no idea what you are asking for the second question. What is k?
    I believe little o is that the limit equals zero. Big-O is that the limit is finite and nonnegative (and may be zero). Big-Theta is that the limit is finite and greater than zero.
    Last edited by SlipEternal; Nov 9th 2017 at 11:25 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2017
    From
    LA, USA
    Posts
    4

    Re: Proving Big O using Mathematics/Functions

    k is positive integers, so 1, 2, 3, [...], n
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,971
    Thanks
    1141

    Re: Proving Big O using Mathematics/Functions

    Quote Originally Posted by kazuki00 View Post
    k is positive integers, so 1, 2, 3, [...], n
    If k is a set of positive integers, then I understand even less. How do you apply C to the set of all positive integers 1 to n? Or is it just a random integer in that range? If it is random, are all of the possible values for k equally likely?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    1,118
    Thanks
    467

    Re: Proving Big O using Mathematics/Functions

    I assume your question about quicksort is the time complexity of same. Your recursive formula for C, the average number of comparisons executed by quicksort, is not quite right. I recommend the Wikipedia article on quicksort, specifically the sections on complexity -- https://en.wikipedia.org/wiki/Quicksort
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proving three different functions
    Posted in the Calculus Forum
    Replies: 3
    Last Post: Sep 30th 2012, 02:39 PM
  2. Replies: 1
    Last Post: Aug 17th 2012, 12:24 AM
  3. proving functions onto
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Oct 28th 2010, 08:02 AM
  4. Proving functions
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: Feb 17th 2009, 07:27 AM
  5. Mathematics: Discrete-Mathematics (Algorithems)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Nov 2nd 2008, 07:27 AM

Search Tags


/mathhelpforum @mathhelpforum