Big O complexité lorsque deux fonctions f (n) [O (1)] et g (n) [O (n)] sont multipliées ensemble

Question

f (n) et g (n) représentent le temps de fonctionnement de deux algorithmes différents . f (n) a une complexité d'algorithme O (1), et g (n) a une complexité d'algorithme O (n). Peut-on prétendre que f (n) * g (n) a une complexité O (n)? Pourquoi pourquoi pas?

Answer 1

Une preuve mathématique:

Si nous voulons la preuve que f (n) * g (n) est O (n), nous devons montrer que existe n0 et constant c tels que:

f(n)*g(n) < c*n for every n>n0 

nous avons en tant que f (n) est O (n) ce qui signifie qu'il y a c1, n1:

f(n)<c1*n for every n>n1 (1) 

et g il y c2, n2:

g(n)<c2 for every n>n2 (2) 

Maintenant, nous avons que, pour chaque n>max(n1,n2) (max parce que nous voulons que les deux inégalités pour f et g à tenir):

f(n)g(n)<c1*c2*n (by multiplying (1),(2)) 

donc nous avons prouvé qu'il ya c=c1*c2 and n0=max(n1,n2) comme le dessous de l'inégalité est vérifiée:

f(n)g(n)<c*n -> f(n)*g(n) is O(n) for every n>n0. 

Answer 2

O (n) est la complexité temporelle. Lorsque nous multiplions f (n) et g (n). La complexité temporelle supérieure l'est donc, la complexité de l'algorithme est O (n).