Большая сложность O, когда две функции f (n) [O (1)] и g (n) [O (n)] умножаются вместе

Question

f (n) и g (n) представляют время работы двух разных алгоритмов , f (n) имеет сложность алгоритма O (1), а g (n) имеет сложность алгоритма O (n). Можем ли мы утверждать, что f (n) * g (n) имеет сложность O (n)? Почему, почему нет?

Answer 1

Математическое доказательство:

Если мы хотим доказательство того, что е (п) * г (п) О (п) мы должны показать, что существует n0 и постоянная c, такие как:

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

Мы имеем как факт, что Р (п) является O (N), что означает, что есть c1, n1:

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

и г есть с2, n2:

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

Теперь мы имеем, что для любого n>max(n1,n2) (макс, потому что мы хотим, чтобы оба неравенства для е и г держать):

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

таким образом мы доказали, что есть c=c1*c2 and n0=max(n1,n2) такие как ниже неравенство:

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

Answer 2

O (n) - сложная задача. Когда мы умножаем f (n) и g (n). Чем выше временная сложность, тем сложнее алгоритм O (n).