FC16 Sample O(N^2) algorithms

Lots of software developers do not have formal computer science training, especially 20 or 30 years ago. One big difference maybe they’re not used to big O notation. Even for those who studied it in CS class, they may forget all about it when they walk out of school into the real world. Big O notation is very useful tool in algorithm design and performance analysis and optimization. I often use it in my performance analysis and writings.

O(N) algorithms are very common, which means the cost of a method is proportional to data size. If you double the data volume, cost also doubles. That is what people normally would expect.

O(1) algorithms are like magic, which means the cost of a method is independent of data size, being almost constants. For example, hash table lookup performance is normally O(1), unless we have bad hash collisions or dictionary corruption.

O(N²) algorithms are the bad guys, which means if you double input size, cost will quadruple. It’s important that you find and fix such algorithms as soon as possible.

Here are a few simple O(N²) algorithms:

Try to understand why they’re O(N²) and how to fix them.