CODEWITHSUNDEEP
algorithmtime-complexitybig-o
user1861872
user1861872

Reputation: 91

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)?

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

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

Will that be correct?

Upvotes: 0

Views: 50

Answers (1)

user1196549
user1196549

Reputation:

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.

Upvotes: 1

Related Questions