O(2^N) denotes an algorithm whose growth will double with each additional element in the input data set. The execution time of an O(2^N) function will quickly become very large.

I read this article. But unfortunately this article does not have any example for O(2^N). May you give me code example and describe more?

The Fibonacci number -if coded as a recursion- has exponential growth. (It doesn't matter whether it's 2^n, 3^n or 10^n, by the way - if growth is exponential then the base usually doesn't make a big difference.)

Another common source of exponential-time algorithms is when you perform a brute-force search for something. For example, if you try to factor a number by testing all potential divisors, you'd have O(2^n) iterations for an n-bit number.

It's maybe worth mentioning that big-O notation is used to specify upper bounds, so that an algorithm which runs in O(n) time also (trivially) runs in O(2^n) time. That might seem like peculiar use of notation, but sometimes you might have an upper bound for something and not know if it's a tight upper bound. Big-omega notation is used to indicate that something requires at least the specified amount of a resource, and big-theta indicates that the bound is tight (it's both big-O and big-omega).

O(2^N) denotes an algorithm whose growth will double with each additional element in the input data set. The execution time of an O(2^N) function will quickly become very large.

I read this article. But unfortunately this article does not have any example for O(2^N). May you give me code example and describe more?

Thanks

I was searching for the same thing a while ago...realized i would need it much later, so just skimmed the article below...check this link out and let me know if if you like it (plain-english-explanation-of-big-o) :

PS : if you like it, then i guess i will peruse it in the future.
Also, it seems that DS and algo books ( in java especially) are generally difficult to understand because they focus too much on the theory and mathematics. Do you feel the same ?

SCJP 6. Learning more now.

abalfazl hossein
Ranch Hand

Joined: Sep 06, 2007
Posts: 635

posted

0

This code calculate Fibonacci nth number.

Now my question is:

How do you know Big o of this?

How is it O(2^n) ?

Do you feel the same ?

Yes, I don't know why a person who must be a developer or programmer must know many things about math, as Integral and so on..

We know which complexity it runs in because we have tried it before, and it is a classic example of exponential cpomplexity. And as befits Fibonacci numbers, it runs in 1.618^n time.

Yes, I don't know why a person who must be a developer or programmer must know many things about math, as Integral and so on..

It's certainly important for a programmer to be aware of these things.

Suppose that you are writing a program and you need a collection class. How are you going to decide which collection class is the appropriate one to use for your program? You will have to know something about the characteristics of the different collection classes to be able to decide this.

For example, getting an element by index of an ArrayList is an O(1) operation - it takes a constant amount of time, no matter how many elements there are in the list. But getting an element by index of a LinkedList is an O(n) operation - it takes an amount of time that is proportional to the number of elements in the list (so on a long list it takes longer). On the other hand, inserting an element in the middle of the list is O(n) for ArrayList and O(1) for LinkedList, so for that operation LinkedList is more efficient.

So, you have to think about what operations your program does, and then find out if an ArrayList or a LinkedList is the most efficient one for your program.

Likewise, if you are implementing algorithms that work on large data structures you have to be aware of the characteristics of the algorithm. An O(n^2) algorithm may work fine if the data set is not too large, but it quickly becomes very slow or uses too much memory when the data set gets bigger. Suppose that you tested your program with a small data set of 10 items. It takes 10^2 = 100 units of time to run. But now your client is going to run it on a real data set with 1,000 items. Now it suddenly takes 1,000^2 = 1,000,000 units of time to run (100,000 times as long!). If you don't know that the algorithm is O(n^2) then you're going to be wondering for a long time why it takes too long when the client runs it.

Abalfazl, we know the complexity of the algorithm through mathematical analysis. Informally, you could look at it like this:

For n=1, fib() is run 1 time.
For n=2, fib() is run 3 times.
For n=3, fib() is run 5 times.
For n=4, fib() is run 9 times.
For n=5, fib() is run 15 times.
For n=6, fib() is run 25 times.

You can see that the times fib() is invoked, increases exponentially with n. The way I describe it here lacks mathematical rigor, but it gives you an idea.
We learn maths so we can calculate it properly ;)

You already provided the Fibonacci code yourself. It is O(c^n), which is really the same thing as O(2^n). It doesn't matter which value you take for c, they all describe the same complexity class.

Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 42931

68

posted

0

Stephan van Hulst wrote:I'm guessing he's still referring to O(c^n).

Ah yes, that's possible. A good example of how important it is in software development (as in so many other areas) to pay attention to detail. Typing in "n^2" if you really mean "2^n" is the sort of mistake that occasionally gets rockets and spacecraft blown up :-)

What the poster did there is called a proof by induction. I'm not going to explain it to you here, you will either have to pick up a discrete mathematics book or find a link on the web to explain it to you.

Yes, that is more or less how you can reason about Big O notation.

The question that Big O notation answers is: If n becomes large, then how does the performance (in for example number of computations needed, or amount of memory needed) of the algorithm grow?

Maybe it's easier to see if you fill in concrete numbers for n. If you have a list of 100 items, how many operations does bubble sort have to do to sort the list? What if you have 1,000 items, or 10,000 or 100,000? Suppose that the algorithm needs some constant amount of setup time + a number of operations that is 2^n the number of elements in the list, you'll see that the constant setup time becomes negligible compared to the 2^n operations as n becomes bigger. So, that's why you can say "O(1) + O(2^n) = O(2^n)". Note that Big O notation does not give you an exact number of operations, it just tells you how many operations approximately are necessary for an algorithm, and how the number of operations grows as the input gets larger.

abalfazl hossein
Ranch Hand

Joined: Sep 06, 2007
Posts: 635

posted

0

Thanks Jesper.

Other than fibonacci, Do you know code example for O(2^n)?

according to the wikipedia, these are both O(c^n):

Finding the (exact) solution to the traveling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors