aspose file tools*
The moose likes Java in General and the fly likes Big O Notation Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Big O Notation" Watch "Big O Notation" New topic
Author

Big O Notation

abalfazl hossein
Ranch Hand

Joined: Sep 06, 2007
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.


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
Marshal

Joined: Mar 22, 2005
Posts: 42292
    
  64
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.)


Ping & DNS - my free Android networking tools app
Kurt Van Etten
Ranch Hand

Joined: Sep 07, 2010
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

Joined: Jan 21, 2011
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.


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

Joined: Sep 06, 2007
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

Joined: Oct 13, 2005
Posts: 39436
    
  28
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

Joined: Oct 13, 2005
Posts: 39436
    
  28
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

Joined: Sep 06, 2007
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

Joined: Aug 16, 2005
Posts: 14274
    
  21

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.

Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 8 API documentation
abalfazl hossein
Ranch Hand

Joined: Sep 06, 2007
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).

Thanks in advance friends
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 42292
    
  64
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

Joined: Sep 20, 2010
Posts: 3647
    
  17

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

Joined: Sep 06, 2007
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

Joined: Sep 20, 2010
Posts: 3647
    
  17

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: 42292
    
  64
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

Joined: Sep 06, 2007
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

Joined: Sep 20, 2010
Posts: 3647
    
  17

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
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39436
    
  28
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

Joined: Sep 06, 2007
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

Joined: Aug 16, 2005
Posts: 14274
    
  21

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

Other than fibonacci, Do you know code example for O(2^n)?
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11422
    
  16

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

Joined: Sep 06, 2007
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
 
 
subject: Big O Notation