# Big O Notation

abalfazl hossein

Ranch Hand

Posts: 635

posted 5 years ago

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

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

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

Ulf Dittmer

Rancher

Posts: 42968

73

posted 5 years ago

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

posted 5 years ago

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

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

posted 5 years ago

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.

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 ?**

SCJP 6. Learning more now.

abalfazl hossein

Ranch Hand

Posts: 635

Campbell Ritchie

Sheriff

Posts: 50180

79

Campbell Ritchie

Sheriff

Posts: 50180

79

abalfazl hossein

Ranch Hand

Posts: 635

posted 5 years ago

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

posted 5 years ago

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

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

Ulf Dittmer

Rancher

Posts: 42968

73

Stephan van Hulst

Bartender

Posts: 6319

78

posted 5 years ago

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

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

abalfazl hossein

Ranch Hand

Posts: 635

posted 5 years ago

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)

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

78

posted 5 years ago

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

73

posted 5 years ago

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

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

posted 5 years ago

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-

May you explain this simply?

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

78

posted 5 years ago

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

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

Campbell Ritchie

Sheriff

Posts: 50180

79

posted 5 years ago

Google for bubble sort. You can write a program to test it in about ten minutes.abalfazl hossein wrote:I want an example for this : O(2^n) . . .)

abalfazl hossein

Ranch Hand

Posts: 635

posted 5 years ago

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

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

posted 5 years ago

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.

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

posted 5 years ago

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

abalfazl hossein

Ranch Hand

Posts: 635

posted 5 years ago

Thank you very much,

With all due respect,

Campbell Ritchie wrote:No, it calculates the (abalfazl hossein wrote: . . . This code calculate Fibonacci nth number. . . ..n+ 1)thmember of the commonest fibonacci series.

Thank you very much,

With all due respect,

http://en.wikipedia.org/wiki/Bubble_sortBubble sort has worst-case and average complexity both О(n^2),