Big O Notation

Big O is a crucial topic that should not and can not be overlooked while learning data structures and algorithms. One of the most basic methods for computer scientists to assess the cost and complexity of an algorithm is Big O notation.

Time Complexity

The Time Complexity of an algorithm defines how the runtime of your program changes with changing input size.

O(n), where n is the size of the file. This means that the time it takes to transfer a file grows in direct proportion (linearly) to its size.

There are several other runtimes. O( log N), O(N log N), O( N), O( N 2 ), and O( 2N) are some of the most frequent. However, there is no definitive list of potential runtimes.

Complexity Growth Chart from Big O Cheatsheet

• The least complicated one is O(1), often referred to as “constant time”.
• O(log(n)) is more complex than O(1), but not as much as polynomials.
• Polynomials become more complex as the exponent rises.
• As long as the coefficients are positive multiples of n, exponentials are more complicated than polynomials.
• Factorials are more complex than exponentials.

Big O, Big Theta, and Big Omega

O (big O): Big O describes an upper bound on time. It is regarded as the Worst Case. Assume we are looking for a number in an array. If the element we are looking for is the last or not present in the array, we iterate over all of the array’s elements to confirm this.

Ω (big omega): Big Ω describes a lower bound on the time. It is considered as the Best Case if the number we are searching for is the first element in the array.

Ɵ (big theta): Big Ɵ describes a range between upper and lower bounds. It is also regarded as the Expected / Average Case.

Space Complexity

The Space Complexity of an algorithm describes how your program’s memory usage varies as the size of the input changes. Space complexity includes both auxiliary (temporary) space and space used by input. We should constantly strive to write algorithmic code with the least amount of space complexity possible.

n = int(input("n "))
sum = 0
for i in range(n):
    sum+=i
# in this case the Space complexity is O(1)

We frequently omit constants and Non-Dominant Terms.

• O (n⁵ + n) → O (n⁵ )
• O (n + 1) → O (n )

Algorithms with Multiple Parts

for i in range(n):
    i+=1
for j in range(m):
    j+=1

In the above example, we do n amount of work then m amount of work. Therefore, the total amount of work is O(n+m).

for i in range(n):
    i+=1
    for j in range(m):
        j+=1

In the above example, we do m amount of work for n times. Therefore, the total amount of work is O(n X m).