CODEWITHSUNDEEP
mathruntime
plsdontbeangry
plsdontbeangry

Reputation: 55

Is O(N+N) the same as O(2N) in Big O Notation?

If I have a program with two simple loops and nothing else, giving me O(N+N). With time complexities Big O Notation are we allowed to simplify O(N+N) as O(2N)? If not, do how do both differ in terms of time complexity. I apologize for the simple question but just got into studying these concepts and my study guide keeps using O(N+N) instead of O(2N), which is confusing me.

Upvotes: 0

Views: 371

Answers (1)

Illia Bobyr
Illia Bobyr

Reputation: 780

Big O notation is a very well known concept, and so there are tons of material available online. One Google search away. Not really sure why would you ask here.

In particular, Wikipedia has a very long article: https://en.wikipedia.org/wiki/Big_O_notation

And there is a section on how sums work with this notation: https://en.wikipedia.org/wiki/Big_O_notation#Sum

One common misunderstanding is to assume that = in the notation actually is an equality operation. While, in fact, it is a set element operation, more commonly written as ∈.

Technically, you should be writing f(x) ∈ O(N). Writing f(x) = O(N) is wrong, as O(N) is really a set of functions. It is a set of all the functions that grow as fast as the linear function.

A sum of two functions that grow as fast as a linear function also grows as fast as a linear function.

O(f) is a set of functions that grow as fast as f. Both O(N+N), and O(2N) are the same sets as O(N). So, O(N+N) = O(2N) = O(N) and here, this = is really the set equality operation.

Upvotes: 1

Related Questions