Big O Notation

http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

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

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).

abalfazl hossein wrote:http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

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) :

http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html

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 ?

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.

abalfazl hossein wrote: . . . This code calculate Fibonacci nth number. . . ..

No, it calculates the (n + 1)th member of the commonest fibonacci series.

I want an example for this : O(2^n)

an example that shows how big O of a code calculate as O(2^n)

abalfazl hossein wrote:

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..

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.

Thanks Jesper!

Please in a real java code program, a simple program, Show me how the Big o of that code is O(n^2)?

My problem is O(n^2), I don't know how Big of a code be O(n^2).and How to calculate Big o of that code.

I understand other Big o in this site:
http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

But unfortunately has not example for O(n^2).

Thanks in advance friends

abalfazl hossein wrote:But unfortunately has not example for O(n^2).

It sure does. Do you have a question about the example?

I'm guessing he's still referring to O(c^n).

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 ;)

I don't see any example for O(2^n) in this site:

http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

I need example with a simple java code to describe about O(2^n)

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.

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 :-)

Assume T(n-1) = O(2n-1), therefore

T(n) = T(n-1) + T(n-2) + O(1) which is equal to

T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)

http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence

1- Why T(n-1) = O(2^n-1)?

2-Why T(n) = O(2^n-1) + O(2^n-2) + O(1) = O(2^n)

3-

Alternatively, you can draw the recursion tree, which will have depth n and intuitively figure out that this function is asymptotically O(2^n).

May you explain this simply?

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.

Here is a Wikipedia article on it: http://en.wikipedia.org/wiki/Mathematical_induction
I warn you though, if you're not mathematically inclined, this will probably just confuse you more.

[edit]
The page is also available in simple english: http://simple.wikipedia.org/wiki/Mathematical_induction

abalfazl hossein wrote:I want an example for this : O(2^n) . . .)

Google for bubble sort. You can write a program to test it in about ten minutes.

Ok, This is what I understand:

When we want to know Big O, We consider the worst situation.

T(n) = O(2^n-1) + O(2^n-2) + O(1) = O(2^n)

O(2^n) is greater than O(2^n-1) and O(2^n-2),

Then I can say:

T(n)=O(2^n) +O(2^n) +O(1)=O(2^n)

Right?

But there is question for me: How to assume T(n-1) = O(2^n-1)?

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.

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

Campbell Ritchie wrote:

abalfazl hossein wrote: . . . This code calculate Fibonacci nth number. . . ..

No, it calculates the (n + 1)th member of the commonest fibonacci series.

Thank you very much,

With all due respect,

Bubble sort has worst-case and average complexity both О(n^2),

http://en.wikipedia.org/wiki/Bubble_sort