CODEWITHSUNDEEP
time-complexitybig-ocomplexity-theory
benlaug
benlaug

Reputation: 2771

Can O(N+NM) be simplified to O(NM)?

Suppose that N and M are two parameters of an algorithm. Is the following simplification correct?

O(N+NM) = O[N(1+M)] = O(NM)

In other words, is it allowed to remove the constant in such a context?

Upvotes: 1

Views: 2146

Answers (2)

joanis
joanis

Reputation: 12260

TL;DR Yes

Explanation

By the definition of the Big-Oh notation, if a term inside the O(.) is provably smaller than a constant times another term for all sufficiently large values of the variable, then you can drop the smaller term.

You can find a more precise definition of Big-Oh here, but some example consequences are that:

  • O(1000*N+N^2) = O(N^2) since N^2 will dwarf 1000*N as soon as N>1000

  • O(N+M) cannot be simplified

  • O(N+NM) = O(NM) since N+NM < 2(NM) as soon as N>1 and M>1

Upvotes: 4

Leandro Caniglia
Leandro Caniglia

Reputation: 14868

Obviously, you cannot get rid of the N term if M=0. so let's assume M>0. Take a constant k > 0 such that 1<=kM (if M is integer, k=1, otherwise take a constant c such that 0 < c <= M an take k=1/c). We have 

N+NM  = N(1+M)
     <= N(kM+M)            ; 1<=kM
      = (k+1)NM
      ∊ O(NM)

On the other hand,

NM <= N+NM ∊ O(N+NM)

Hence the equality.

Upvotes: 4

Related Questions