Exponential time complexity

Question

Hi, I have been working on finding an example of an algorithm having exponential time complexity. I have searched google a lot but could not understand it better.
Can anyone give me a simple example of exponential time complexity of an algorithm.
Or may be a link that can help me.

Answer 1

Treerecursive functions that marginally reduce the size of their argument are candidates for exponential runtime.
For example, the following function that constructs an ummarked binary tree (code in SML) has the complexity O( 2^n ):

fun btree ( 0 ) = nil
| btree ( n ) = [ btree ( n - 1 ), btree ( n - 1 ) ]

This is a naive implementation that could be optimized to linear complexity, but it serves as an example. Since we have two recursive calls to btree() in each step, the cost grows exponentially.
Another example would be the fibonacci function

fun fib ( n ) = if n < 2 then n else fib ( n - 1 ) + fib ( n - 2 )

which has exponential complexity as well, although not quite O( 2^n ).
In terms of a loop, I think the following loop would have exponential complexity:

for ( unsigned i{ 0 }; i < ( 1u << n ); ++i )
{
// ...
}

Although you would get overflow issues quickly.

Answer 2

Can a simple for loop have exponential time complexity like
for(int i=0;i<n;i=i*2) has time complexity of log(n)

Answer 3

#define CPP ChillPill