Why do Exponential Functions Hurt?
Before we move further, let us recap the types of time complexity functions we have encountered till now. We will also see that algorithms with exponential functions are evil.
Here is the list of functions we have seen till now.
O (1) // constant
O (log n) // logarithmic
O (sqrt (n)) // square root of n
O (n) // linear, degree of 1
O (n^2) // quadratic, degree of 2
O (n^3) // cubic, degree of 3
O (n^n) // exponential
The sequence of these functions is the same as written above. That is, a quadratic equation is larger than a logarithmic function.
In the following table, we will take some example values of n to see how these functions behave.
n | log n | n^2 | n^3 | 2^n |
1 | 0 | 1 | 1 | 2 |
2 | 1 | 4 | 8 | 4 |
4 | 2 | 16 | 64 | 16 |
8 | 3 | 64 | 512 | 512 |
16 | 4 | 256 | 4096 | 65536 |
32 | 5 | 1024 | 32768 | Won’t fit here |
Leave a Reply