In our last tutorial we learnt about Quadratic time complexity O(n^{2}). If you have not read that article I would suggest you to read it first.

Quadratic time complexity O(n^{2})

#
What is Exponential Time Complexity O(c^{n})?

In exponential time algorithms, the growth rate doubles with each addition to the input (n). Let's look at the chart:

Let's take following example:

function pow(c, n) { if (n === 0) return 1; return c * pow(c, n-1); } console.log(pow(2, 2)); // 4

When we analyze time complexity of above function:

- each simple operation cost 1 unit of time i.e. comparison, multiplication, substraction etc..
- we can ignore other small operations like return statement

Looking at the function we are seeing that there are two conditions here:

- when n=0
- final condition when n=n-1

Here is the function call diagram:

Let say that for above function if we write the equation it would be:

Let say to calculate time complexity of pow(c, n-1) = T(n-1) Other simple operations that happens in that function is c T(n) = T(n-1) + c where n > 0 and c = some constant that we need to perform simple operations T(0) = 1 when n=0 function returns 1 If you want to find: T(2) = T(n-2) + 2c T(3) = T(n-3) + 3c T(k) = T(n-k) + kc n-k = 0 for base case then k = n T(n) = T(n-n) + nc = T(0) + nc = 1 + nc because T(0) = 1 T(n) = O(n) considering bigger term from the equation and ignoring other constants

Therefore, total complexity of the statement: c * pow(c, n-1) = O(c^{n}) which is a bigger term when analyzing out function complexity.