Example of a O(2^N) algorithm

Question

I've been told that

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

Can someone provide an example that behaves like this?

It's not an algorythm. This is Big O notation for rating algorythm complextity — Donz, Apr 06 '11 at 12:21
It's clear that he's trying to understand the concept of `O(2^n)`, and what that may look like in practice. — Travis Webb, Apr 06 '11 at 12:23
Even after providing clear explanation, not answering and voting it for negative and voting it for "close the question" is not fair — developer, Apr 06 '11 at 12:25
if i metion "waht or how" then only it will be considered as good question, its funny comment. Also i clarifed "can anyone help in this algorithm". Please read the question properly — developer, Apr 06 '11 at 13:13
@Damodar: I've taken a crack at making your question agree with the answer that you accepted. I hope that this is what you meant, but I don't actually *know*. That uncertainty is probably the source of the negative reaction you received: despite Travis' feelings on the matter I found your question very unclear. Presumably the closers were in a similar position. — dmckee --- ex-moderator kitten, Apr 07 '11 at 00:22

score 18 · Accepted Answer · edited May 23 '17 at 12:01

18

Recursive computation of Fibonacci numbers is a good example of O(2^N) algorithm (though O(2^N) is not a tight bound for it):

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

edited May 23 '17 at 12:01

Community

answered Apr 06 '11 at 12:41

axtavt

Can you please tell me how to make difference between O(2^n) and O(log n) ? – Ahmed Hamdy May 29 '14 at 20:32
check this answer. http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly – Jinbom Heo Jul 09 '14 at 01:22

1 Answers1