Algorithms — Big O Notation

Big O Notation is a mathematical function that helps us analyze how complex an algorithm is in time and space. It matters when we build an application for millions of users.

We usually implement different algorithms to solve one problem and measure how efficient one is with respect to the other ones.

Time and Space Complexity

Time complexity is related to how many steps take the algorithm.

Space complexity is related to how efficient the algorithm is using the memory and disk.

Both terms depend on the input size, the number of items in the input. We can analyze the complexity based on three cases:

· Best case or Big Omega?Ω(n): Usually, the algorithm executes independently of the input size in one step.

· Average case or Big Theta?Θ(n): When the input size is random.

· Worst-case or Big O Notation?O(n): Gives us an upper bound on the runtime for any input, and it gives us a kind of guarantee that the algorithm will never take any longer with new input size.

Order of Growth of Common Algorithms

The order of growth is related to how the runtime of an algorithm increases when the input size increases without limit and tells us how efficient the algorithm is. We can compare the relative performance of alternative algorithms. The Figure below shows Big O Notations of common algorithms.

Big O Notations examples:

O(1) — Constant

It does not matter if the input contains 1000 or 1 million items. The code always executes in one step.

O(N) — Linear

Our algorithm runs in O(N) time if the number of steps depends on the number of items included in the input.

O(N2) — Quadratic

When we have two loops nested in our code, we say it runs in quadratic time O(N2). For example, when a 2D matrix is initialized in a tic-tac-toe game.

O(N3) — Cubic

We say that our algorithm runs in Cubic time when the code includes at the most three nested loops. For example, given N integers, how many triples sum to precisely zero? One approach (not the best) is to use three nested loops.

O(LogN) — Logarithmic

This kind of algorithm produces a growth curve that peaks at the beginning and slowly flattens out as the size of the input increase.

Log28 = 3

Log216 = 4

Log232 = 5

The?binary search?uses at most LogN key compares to search in a sorted array of size N. With eight elements, it takes three comparisons, with 16 elements takes four comparisons, with 32 elements takes five comparisons, and so on.

How to Find the Time Complexity of an Algorithm

To find the Big O complexity of an algorithm follows the following rules:

· Ignore the lower order terms

· Drop the leading constants

Example: If the time complexity of an algorithm is 2n3 + 4n + 3.

Its Big O complexity simplifies to O(n3).

Example: Given the following algorithm:

First, we split the code into individual operations and then compute how many times it is being executed, as is shown in the following table.

Now, we need to sum how many times each operation is executing.

Time complexity = 1 + 1 + N + N + N + N + 1 => 4N + 3

Big O complexity = O(N)

Why Big O Notation ignores Constants?

Big O Notation describes how many steps are required relative to the number of data elements. And it serves as a way to classify the long-term growth rate of algorithms.

For instance, O(N) will be faster than O(N2) for all amounts of data, as shown in the figure below.

O(N) is faster than O(N2) for all amounts of data

Now, if we compare O(100N) with O(N2), we can see that O(N2) is faster than O(100N) for some amounts of data, as shown in the figure below.

O(N2) is faster than O(100N) for some amounts of data

But after a point, O(100N) becomes faster and remains faster for all increasing amounts of data from that point onward. And that is the reason why Big O Notation ignores constants. Because of this, O(100N) is written as O(N).