CODEWITHSUNDEEP
algorithmbig-o
John
John

Reputation: 3115

Is O(n+m) equal to O(n) if m is known to be less than n in all cases?

I may have the notation wrong. I think this because are not constants ignored in big O notation? I'm pretty new to all this algorithmic analysis stuff. Any help would be greatly appreciated?

I'm going through an array, keeping track of counts in another array and then going over that second array keeping track of running counts.

Upvotes: 1

Views: 172

Answers (1)

Thilo
Thilo

Reputation: 262774

Yes. If m is always at most n, then O(n+m) is O(n+n) is O(2n) is O(n).

As @phs points out in the comments, this is even the case if m is at most X*n (for a fixed X): Then O(n+m) is O(n+X*n) is O(Y*n) is O(n).

Upvotes: 5

Related Questions