Algorithm example O (2 ^ N)

Question

I was told that

O (2 ^ N) denotes an algorithm whose growth doubles with each additional element in the input data set

Can anyone provide an example that behaves as follows?

Answer 1

The recursive calculation of Fibonacci numbers is a good example of the O (2 ^N ) algorithm (although O (2 ^N ) is not dense for it ):

public int fib(int n) {
    if (n <= 1) return n;
    else return fib(n - 2) + fib(n - 1);
}