Evaluating runtime complexity
Now that you have the big picture in mind, let's look at some real data for the time performance of common Big-O functions so you will definitely understand the magnitude of the different orders. These running times are done in a faster computer where a simple instruction takes just one nanosecond. Take a look at the following table:
Big-O types and performance – running times for different inputs
The grayed section is colored because the times are not practical in real-world applications. Any algorithm with a running time of more than 1 second is going to have an impact in your application. So by looking at the data provided by this table, some conclusions arise:
- For a very tiny n (n < 10), almost any order function works quick
- Algorithms that run on log(n) can have a huge amount of data without becoming slow at all
- Linear and n*log(n) algorithms have a great performance for huge inputs
- Quadratic functions (n2) start to have bad performance...
