Drop The Constants And Non Dominant Terms In Big O

[!INFO]-
topic: 🖥️ Tech
links: Big O Notation
source: Cracking the Coding Interview
tags: #permanent-note #published

Last Modified: =dateformat(this.file.mtime, "MMM. dd, yyyy - HH:mm")

Ignore constants and non-dominant terms in Big O.
O(2N) = O(N)
O(N² + N) = O(N²)

When expressing something in the Big O notation, simply ignore constants. An algorithm that can be described with O(2N) is the same as O(N). We often tend to express an algorithm with two for loops as O(2N), but you can't really compare it to one solution with one for loop but more complex code in each iteration because the complexity of the instructions on assembly level might differ. To simply this, just ignore the constants.

If we say O(2N²) = O(N² + N ²) = O(N²) because we ignore the constants, then we certainly don't care about the N in O(N² +N). So O(N² + N) = O(N²).