algorithm - Example of Big O of 2^n -

so can picture algorithm has complexity of n^c, number of nested loops.

for (var = 0; < dataset.len; i++ {     (var j = 0; j < dataset.len; j++) {         //do stuff , j     } } 

log splits data set in half every time, binary search (not entirely sure code looks like).

but simple example of algorithm c^n or more 2^n. o(2^n) based on loops through data? or how data split? or else entirely?

algorithms running time o(2^n) recursive algorithms solve problem of size n recursively solving 2 smaller problems of size n-1.

this program, instance prints out moves necessary solve famous "towers of hanoi" problem n disks in pseudo-code

void solve_hanoi(int n, string from_peg, string to_peg, string spare_peg) {     if (n<1) {         return;     }     if (n>1) {         solve_hanoi(n-1, from_peg, spare_peg, to_peg);     }     print "move " + from_peg + " " + to_peg;     if (n>1) {         solve_hanoi(n-1, spare_peg, to_peg, from_peg);     } } 

let t(n) time takes n disks.

we have:

t(1) = o(1) , t(n) = o(1) + 2*t(n-1) when n>1 

if repeatedly expand last term, get:

t(n) = 3*o(1) + 4*t(n-2) t(n) = 7*o(1) + 8*t(n-3) ... t(n) = (2^(n-1)-1)*o(1) + (2^(n-1))*t(1) t(n) = (2^n - 1)*o(1) t(n) = o(2^n) 

to figure out, have know patterns in recurrence relation lead exponential results. t(n) = ... + c*t(n-1) c > 1means o(x^n). see:

https://en.wikipedia.org/wiki/recurrence_relation