Asymtotic Complexity

Any code we write should execute in a reasonable amount of time with limited computing resources. Solving problems with tiny inputs is trivial. So we need a mathematical framework to understand how fast our code runs as the input size grows.

Rate of Growth

Let’s use a calculator and play with a few math functions. We will compute $f(x)$ for inputs 1, 5, 10, 20, 25, 100.

Constant function

$$f(x)=600$$

Always returns a constant value. This function doesn’t grow and is independent of input size.

Linear function

$$f(x)=x$$

Returns the input without changing it.

f(1) = 1
f(5) = 5
...
f(100) = 100

Square

$$f(x)=x^2$$

f(1) = 1
f(5) = 25
...
f(100) = 10000

Exponential function

$$f(x)=2^x$$

f(1) = 1
f(5) = 32
...
f(100) = 126...(31 digits)

Logarithmic function

$$f(x)={\log }_2(x)$$

f(1) = 0
f(5) = 2.3...
f(10) = 3.3...
...
f(100) = 6.6...

The exponential function grows extremely fast. And its inverse (log) grows insanely slowly. When we analyze how the number of operations and the memory usage of a piece of code grow w.r.t input size, we prefer slow growing functions.

• If it can run in constant or Logarithmic time, it’s excellent.
• If it’s linear or polynomial of n, then it can be acceptable.
• If it is exponential then we will quickly run out of computing resources as input size grows.

Depending on the problem, we cannot always choose a more efficient algorithm.

Consider only large inputs

Consider the function:

$$f(x)=100,000,000+x^2+8e^x$$

As x becomes very 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$

Asymtotically, i.e. for large values of x, we can write

$$f(x)=\Theta (C^x)$$

It is an exponential function.

Exercise

Is it possible that a piece of code running a linear algorithm runs faster than a logarithmic algorithm? If yes, give an example.