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.