# Thread: Proving Big O using Mathematics/Functions

1. ## 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.)

2. ## 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?

3. ## 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 ?

4. ## Re: Proving Big O using Mathematics/Functions

Originally Posted by kazuki00
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?

5. ## Re: Proving Big O using Mathematics/Functions

Originally Posted by SlipEternal
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.

6. ## Re: Proving Big O using Mathematics/Functions

k is positive integers, so 1, 2, 3, [...], n

7. ## Re: Proving Big O using Mathematics/Functions

Originally Posted by kazuki00
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?

8. ## 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