For an algorithm with a time complexity of O(N+M), if M is always less than N, can we say the time complexity will be O(N)?

Question

Give an algorithm with time complexity of O(N+M) and M

Can we conclude O(N+M) => O(N+N) => O(2N) => O(N)

Will that be correct?

Yves Daoust · Answer

f(N, M) = O(N + M) is by definition

E c, N0, M0: A N ≥ N0, M ≥ M0: f(N, M) ≤ c (N + M)

But by your hypothesis, M < N so that

E c, N0, M0: A N ≥ N0, M ≥ M0: f(N, M) ≤ c (N + M) < c 2N

and

E c', N0, M0: A N ≥ N0, M ≥ M0: f(N, M) ≤ c' N.