What is Algorithm Complexity and Big O Notation? | Learn DSA

What is an Algorithm complexity, and how do we measure it in the context of algorithms?

Answer:

For the same problem and same inputs, different algorithms takes different time to solve.

Sometimes the huge difference in time, especially when no of elements to manage grows.

This complexity is called Big O, the Big O can be measured in following ways followed by more efficient to less efficient.

• O(1)
• O(log n)
• O(n)
• O(n * log n)
• O(n^2)
• O(n!)

Where n is the number of inputs. For example, if we want to sort 2 items n is 2, and if we want to sort 20,000 items n is 20,000.

We don’t substitute any value in the O() calculation. It’s just to understand that it’s an efficiency in the algorithm.

The best algorithm should have the O(1) efficiency. The time taken to execute such algorithm does not depend on the number of inputs. Instead for any number of inputs it should take the same time to execute.

An algorithm with O(n) efficiency scales linearly with the number of inputs. Example: for 10 items it takes 1 second, and with 100 items it will take 10 seconds to execute algorithm.

An algorithm with O(n²) efficiency takes 16 seconds for 4 items, and 100 seconds for 10 items.

It’s important to note that Big O notation does not give us all the information we need to judge whether an algorithm will be faster than another algorithm, in particular if their Big O value is the same. In this case, we will need to use other tools as well to test the efficiency.

If you wouldn’t mind give it some claps 👏 👏 since it helped, I’d greatly appreciate it :) Help others find the article, so it can help them!

Always be clapping…