Going deeper

To give you an idea:

• A search in a good hash table gives an element in O(1)
• A search in a well-balanced tree gives a result in O(log(n))
• A search in an array gives a result in O(n)
• The best sorting algorithms have an O(n*log(n)) complexity.
• A bad sorting algorithm has an O(n2) complexity

Note: In the next parts, we’ll see these algorithms and data structures.

There are multiple types of time complexity:

• the average case scenario
• the best case scenario
• and the worst case scenario

The time complexity is often the worst case scenario.

I only talked about time complexity but complexity also works for:

• the memory consumption of an algorithm
• the disk I/O consumption of an algorithm

Of course there are worse complexities than n2, like:

• n4: that sucks! Some of the algorithms I’ll mention have this complexity.
• 3n: that sucks even more! One of the algorithms we’re going to see in the middle of this article has this complexity (and it’s really used in many databases).
• factorial n : you’ll never get your results, even with a low amount of data.
• nn: if you end-up with this complexity, you should ask yourself if IT is really your field…

Note: I didn’t give you the real definition of the big O notation but just the idea. You can read this article on Wikipedia for the real (asymptotic) definition.