"Big Oh": Is my reasoning right?

Publish Date: Jul 23 '19

3 5

Apologies for bad notation. Also, I'm not a native speaker.

I started reading this book:

I am currently reading the first chapter, which is about time complexity / asymptotic notation.

So I'm told that for an algorithm whose running time is described by the function 𝑇(𝑛) = 3𝑛³ + 2n² we have a worst-case complexity of O(𝑛³). Fine.

I'm told that I can easily prove that T(n) ≤ 5𝑛³. Fine. (I'm pretty confident in my highschool maths skills.)

Basically, I ended up with T(𝑛) ≤ 3.0...01𝑛³ for 𝑛 tends to +∞. A different value of 𝑐.

It might sound dumb that 3𝑛³ + something could be smaller than 3𝑛³ but I found this using limits.

My reasoning was that, after manipulating the inequality T(n) ≤ 𝑥𝑛³, one could end up with the following statement:

3 + 𝑛^-2 ≤ 𝑥

Now 𝑛 is just a positive integer constant. So let it be 1; smallest input. We end up with 𝑥 = 5. The value provided by the book.

But let's say that 𝑛 gets bigger and bigger; and eventually tends to +∞. Since 𝑛^-2 would then tend to 0, we have 𝑥 tends to 3.

So T(𝑛) ≤ 𝑥𝑛³ with 𝑥 a real number that tends to 3 from upper values but is not exactly 3. In fact, it wouldn't work with 3.

In GeoGebra

Click here if you can't see the video.

C is the point at which 𝑥𝑛³ gets bigger than T(𝑛).

My question

First of all, is my reasoning correct? Can I use this kind of reasoning when dealing with algorithms complexity? I'm pretty confident that it "holds" mathematically speaking but does it apply here?

I understand that it is not really important since we end up with the same O() but still, just curious.

Thank you.

Comments 5 total

Håvard KrogstieJul 23, 2019

Your understanding of limits is correct. As n approaches infinity, c can get closer and closer to 3. n³ is bigger than n² by a factor of n, which means the 2n² part gets closer and closer to negligibly.

Now, the definition of big O states:
T(n) belongs to O(n³) if there exists some finite constants c and n_0 for which every n >= n_0 satisfies T(n) <= c*n³

If n_0 is 1, then c has to be 5, as you showed.

As n_0 gets bigger, c can get closer to 3, as you also showed.

The important part is that there exists some pair of n_0 and c satisfying the requirement.

In fact, if one such pair exists, infinite pairs exist!

Hope this helped, cheers
- Tanguy AndreaniJul 23, 2019
  
  Ok I think I get it now.
  
  Thank you very much!^{^}
  - Håvard KrogstieJul 23, 2019
    
    I'm glad to hear!
    
    If you want some practice, do have a look at a challenge I uploaded
    
    Remove terrible bus routes (find an algorithm)
    
    Håvard Krogstie ・ Mar 9 ・ 2 min read
    
    #challenge #algorithms
    
    .
    The O(n²) solution is trivial, but see if you can come up with one that's O(nlog n) (Hint: sorting). I have posted a python solution in the comments, with explanations. Good luck!
Curtis FennerJul 30, 2019

There's a much more succinct and formal way of putting what I think your reasoning is:

if the limit of f(n) / g(n) is a finite number as n goes to infinity, then f is O(g).

So for example, if you're comparing 3𝑛³ + 2n² to 5𝑛³, the limit of the ratio is 3/5, which is a finite number, so 3𝑛³ + 2n² is O(5𝑛³).

On the other hand, if we compare 10n² and n, the limit is +infinity. So that means 10n² is NOT O(n).
- Tanguy AndreaniJul 30, 2019
  
  Thank you for this. It doesn’t exactly help regarding my reasoning but I think your method is easier to prove that f is O(g). I didn’t know about it so thanks for introducing it to me^{^}

Add comment

Tanguy Andreani @tanguyandreani