Difficulty of Computation
Any code we write should finish in a reasonable amount of time with limited computing resources. Small inputs are trivial. So we need a mathematical framework to understand how slow our code gets with bigger inputs.
Rate of Growth
To get a feel for different difficulties (also called complexity classes), Let's play with a few functions. We will compute \(f(x)\) for inputs 1, 5, 10, 20, 25, 100 to see how fast it grows.
Constant function
Always returns a constant value. This function doesn't grow and is independent of input size.
Linear function
Returns the input without changing it.
f(1) = 1
f(5) = 5
...
f(100) = 100
Square
f(1) = 1
f(5) = 25
...
f(100) = 10000
Exponential function
f(1) = 1
f(5) = 32
...
f(100) = 126...(31 digits)
Logarithmic function
f(1) = 0
f(5) = 2.3...
f(10) = 3.3...
...
f(100) = 6.6...
Let's summarize our findings.
| Function | rate of growth | comment |
|---|---|---|
| \(C\) | doesn't grow | Ideal |
| \(x\) | grows slowly | Good |
| \(x^2\) | grows fast | Acceptable sometimes |
| \(e^x\) | insanely fast | Too difficult |
| \(\log{n}\) | grows insanely slow | Ideal |
Frow now onwards, we will analyze all our code and determine its difficulty level. We can often employ clever techniques to reduce it.
If we cannot, we should stick to small input sizes or look for faster ways to get an approximate answer. Let's say you are making a shooter and the enemies have to find the shortest path to reach you. Considering all possible paths and choosing the shortest will take too long. You have to approximate it maybe they just consider only the next step that takes them closer to you.
Consider only large inputs
Consider the function:
As x becomes large, the constant value \(100,000,000\) will become insignificant in comparison with \(x^2\). We can neglect it in our analysis.
Similarly, \(x^2\) is overshadowed by \(8e^x\). We can absorb 8 into e to form a new constant such that \(8e^x = C^x\)
For large values of x, we can write
which is just a way to say \(f(x)\) grows exponentially for large inputs. What we are doing is known as Asympotic Analysis.
Exercise
Is it possible that a piece of code running a linear algorithm runs faster than a logarithmic algorithm? If yes, give an example.