Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Big O Notation

abalfazl hossein
Ranch Hand
Posts: 635
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.

Thanks

Ulf Dittmer
Rancher
Posts: 42967
73
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.)

Kurt Van Etten
Ranch Hand
Posts: 98
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).

Rahul Sudip Bose
Ranch Hand
Posts: 637
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.

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 ?

abalfazl hossein
Ranch Hand
Posts: 635

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

Campbell Ritchie
Sheriff
Posts: 48972
60
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.

Campbell Ritchie
Sheriff
Posts: 48972
60
abalfazl hossein wrote: . . . This code calculate Fibonacci nth number. . . ..
No, it calculates the (n + 1)th member of the commonest fibonacci series.

abalfazl hossein
Ranch Hand
Posts: 635
I want an example for this : O(2^n)

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

Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15284
39
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.

abalfazl hossein
Ranch Hand
Posts: 635
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).

Ulf Dittmer
Rancher
Posts: 42967
73
abalfazl hossein wrote:But unfortunately has not example for O(n^2).

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

Stephan van Hulst
Bartender
Posts: 5813
61
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 ;)

abalfazl hossein
Ranch Hand
Posts: 635

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)

Stephan van Hulst
Bartender
Posts: 5813
61
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
Rancher
Posts: 42967
73
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 :-)

abalfazl hossein
Ranch Hand
Posts: 635
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?

Stephan van Hulst
Bartender
Posts: 5813
61
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.

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

Campbell Ritchie
Sheriff
Posts: 48972
60
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.

abalfazl hossein
Ranch Hand
Posts: 635
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)?

Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15284
39
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
Posts: 635
Thanks Jesper.

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

fred rosenberger
lowercase baba
Bartender
Posts: 12127
30
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

abalfazl hossein
Ranch Hand
Posts: 635
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