Big O - for anew beginner

Question

Possible Duplicate:
Plain English explanation of Big O

I was recently asked about my knowledge of how to use Big O notation and I was stumped because I had never come across Big O before. I have read the Wikipedia page about Big O and looked at some of the questions posted in Stackoverflow but I just simply don't understand.

My question: Can someone provide an explanation of Big O in the simplest form and provide an example of how to use it in the following Java method:

public int getScore(int[] dice)
{
    int[][] dups;

    dups = possibleDups(dice);

    // Set catScore
    for (int[] i : dups)
    {
        for (int k = 0; k < i.length; k++)
        {
            if (i[k] > 0)
            {
                switch (i[k]) {
                case 1:
                    catScore = Category.ONES;
                    break;
                case 2:
                    catScore = Category.TWOS;
                    break;
                case 3:
                    catScore = Category.THREES;
                    break;
                case 4:
                    catScore = Category.FOURS;
                    break;
                case 5:
                    catScore = Category.FIVES;
                    break;
                case 6:
                    catScore = Category.SIXES;
                    break;
                case 7:
                    catScore = Category.SEVENS;
                    break;
                case 8:
                    catScore = Category.EIGHTS;
                    break;
                default:
                    catScore = Category.NONE;
                    break;
                }
            }
        }
    }

    return sumAll(dice);
}

There are plenty of resources out there explaining Big O and I don't think repeating them is going to benefit you in your understanding of it. So could you specify what exactly it is that you "don't understand"? — tskuzzy, Jul 01 '11 at 15:00
And as for the Big O complexity of your method, it depends on the Big O of possibleDups() and sumAll() so you'd have to provide the definitions of those methods as well. — tskuzzy, Jul 01 '11 at 15:01
I liked the original phrasing of the question, which was something along the lines of, "Big O for a newb" :) — mre, Jul 01 '11 at 15:05
Actually by indicating that i need to provide the other two methods being called in the method itself helps me understand the dependencies it takes to calculate. Thanks. — Curveo, Jul 01 '11 at 15:20
@Curtis Ashby: note that the *switch* case in your example is totally silly. The entire switch can be rewritten much more cleanly in two or three lines of code. Heck, if you're into enums and ternary operator, it can be rewritten in one line. — SyntaxT3rr0r, Jul 01 '11 at 15:47

Edwin Buck · Answer 1 · 2011-07-01T15:17:22.917

Big O notation details the proportional difference in the time of the solution compared to the number of items in a collection. It actually says nothing about how long the solution takes to solve the issue, but it details how quickly the time to solve a solution grows when you know the time for a fixed point and how many other items you are likely to add.

So, if it always takes 5 minutes to make a coffee, it's not enough information to calculate a Big O solution, but if it takes 5 minutes to make a coffee, and five minutes to make ten coffees, and five minutes to make a million coffees, then it is O(1), where the 1 indicates one unit of time.

Now if you have a single cup coffee maker, where it takes roughly two minutes to make a cup of coffee, four minutes to make two cups of coffee, and twenty minutes to make ten cups of coffee, then the time to make a number of coffees is proportional to the number of cups, making the Big O notation O(x), meaning you need X (one for each coffee) units of time.

Other Big O notations are common, O(x^2) O(xlog(x)), etc. They all describe the proportional rate of time increase based on the number of elements in consideration.

Note that O(1) might be slower than an O(x) solution for some small collection of items, as we are talking about units of time, not actual times. So the unit of time in a particular O(1) might be an hour, while the particular unit of time in an O(x) solution might be ten minutes. In such a case, the O(x) solution might be faster until you need to process six or more items. In the long term, big O terms with lower powers (like O(1)) will always outperform those with higher powers O(x) no matter how large or small the actual time units are.

score 2 · Accepted Answer · edited Nov 21 '12 at 16:59

2

Big O is the worst case scenario for an algorithm to execute. You should see how does you loop depend on the inner loop. Sample:

public void doSomething(int n){
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
}

Worst case is 100 times iterate. Change n to 20 and then worst case is 400 iteration.

This is O(n^2).

edited Nov 21 '12 at 16:59

DarkAjax

15,955
11
53
65

answered Jul 01 '11 at 15:03

Zemzela

3,060
6
23
32

1

actually since you hard coded n, it is O(1), it will always be 100. and it is not answering his question. – amit Jul 01 '11 at 15:06
this was just an idea how to calculate O. – Zemzela Jul 01 '11 at 15:07
@amit: so if I write *int n=10000* and then three nested loops, there are 1 000 **billions** execution of the code inside the three loops and yet it's still *O(1)*? I actually **never** thought of the complexity of my algorithms that way, even **all the time when I know my n**. Are you really sure it's correct? I'm not saying it's not correct: it's just silly if it's correct, but so be it should it be correct. – SyntaxT3rr0r Jul 01 '11 at 15:39
@amit: instead of hair-splitting commenting, actually provide something useful to SO. Use your editing power to correct the answer instead of posting comments that won't make any sense anymore after an edit ;) – SyntaxT3rr0r Jul 01 '11 at 15:44
@SyntaxT3rr0r: this is an exaggeration of course, (otherwise I can constraint everything by the time the universe has to live) but the idea is that if you need to iterate over a well defined amount of elements (i.e. 7 days of the week) it is NOT O(n), it is O(1), because the time taken for it is not affected by the input. about your 2nd comment: It is not my place to use the edit to correct answers, but to make them more understandable. who am I to define what is right? that's what comments and up/down votes are for – amit Jul 01 '11 at 15:59
@amit if a don't declare n=10 then the snippet show what I want to show ? – Zemzela Jul 01 '11 at 17:29
@Zemzela: replace `int n=10` with `f(n):`and show as an example, how the runtime varies when you run f(10) [100 ops] and f(100) [10000 ops]. – amit Jul 01 '11 at 17:33
@amit like bubble sorting. It has O(n^2). O(1) is just one statement like assign value to variable, some arithemetic. you say that itaration is O(1) which is actualy O(n). – Zemzela Jul 01 '11 at 17:41
@Zemzela: are you suggesting `sum += 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9;` and `for (int i = 0;i<10;i++) sum+=i;` have different time complexity? – amit Jul 01 '11 at 18:00
@amit yes. Because the first you wrote is constant and will be calculated at build time, second one will be calculated at runtime. – Zemzela Jul 01 '11 at 18:06
@Zemzela let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/1066/discussion-between-amit-and-nesho) – amit Jul 01 '11 at 18:06

hvgotcodes · Answer 3 · 2011-07-01T15:10:10.687

In computer science, a large area of interest is "how long do things take to run?". The answer a lot of the time is "it depends on the size of the input (but it might not)". Big-Oh specifically is a function that describes the upper bound on how long an algorithm with run. There are some mathematical details there (limits, asymptotes, etc), but thats a really basic view.

In your example, you loop over a list, and then for everything in that list, you loop over another list. Therefore, the time your algorithm takes to run is directly proportional to the size of the lists. If you think of a list as having 'n' things in it, and your second list as having m things in it your alogrithm's running time is O(m*n). If m ~ n, then it is also accurate to say O(n^2).

For maps, lookups are constant time (assume they are). In that case, the running time of the Map lookup is therefor O(c) which is the same as O(1).

Big O - for anew beginner

3 Answers3