0

Exponential time complexity

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.

6th Mar 2021, 7:32 PM
HK Lite
HK Lite - avatar
3 Answers
+ 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.
6th Mar 2021, 8:48 PM
Shadow
Shadow - avatar
0
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)
6th Mar 2021, 7:33 PM
HK Lite
HK Lite - avatar
6th Mar 2021, 7:35 PM
HK Lite
HK Lite - avatar