concernant la notation de gros-oh et prouvant ou réfutant

Question

Donc je suis complètement perdu sur la notation de gros-oh.

Dans ma tâche, je suis supposé prouver ou réfuter ce qui suit en utilisant la définition formelle.

3n³ - 7n² + 100n - 36 is in O(n³) 

et

n²/log(n) + 3n is in O(n²) 

quelqu'un peut me aider avec ces derniers et me dire comment s'y prendre pour prouver ou de réfuter.

Answer 1

Le definition of Big-O est

f(n) ∈ O(g(n)) ⇔ lim supn → ∞ | f(n)/g(n) | < ∞

Depuis votre f(n) et g(n) sont polynômes lim sup et lim sont les mêmes. Vous devez donc la preuve:

1. limn → ∞ |(3n³ - 7n² + 100n - 36)/n³| < ∞

    
   limn → ∞ |(3n³ - 7n² + 100n - 36)/n³| 
   = limn → ∞ |n³(3 - 7/n + 100/n² - 36/n³)/n³| 
   = limn → ∞ |3 - 7/n + 100/n² - 36/n³| 
   = 3 < ∞ 
   

2. lim supn → ∞ |(n²/log(n) + 3n)/n²| < ∞

    
   lim supn → ∞ |(n²/log(n) + 3n)/n²| 
   = lim supn → ∞ |n²(1/log(n) + 3/n)/n²| 
   = lim supn → ∞ |1/log(n) + 3/n| 
   = 0 < ∞ 
   

   ici vous pouvez voir aussi que n²/log(n) + 3n est également o(n²).