Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've been learning more about Big O Notation and how to calculate it based on how an algorithm is written. I came across an interesting set of "rules" for calculating an algorithms Big O notation and I wanted to see if I'm on the right track or way off.

Big O Notation: N

function(n) {
    For(var a = 0; i <= n; i++) { // It's N because it's just a single loop
        // Do stuff
    }
}

Big O Notation: N2

function(n, b) {
    For(var a = 0; a <= n; a++) {
        For(var c = 0; i <= b; c++) { // It's N squared because it's two nested loops
            // Do stuff
        }
    }
}

Big O Notation: 2N

function(n, b) {
    For(var a = 0; a <= n; a++) {
        // Do stuff
    }
    For(var c = 0; i <= b; c++) { // It's 2N the loops are outside each other
        // Do stuff
    }
}

Big O Notation: NLogN

function(n) {
    n.sort(); // The NLogN comes from the sort?
    For(var a = 0; i <= n; i++) {
        // Do stuff
    }
}

Are my examples and the subsequent notation correct? Are there additional notations I should be aware of?

share|improve this question
3  
Call it a rule of thumb instead of a formula, and you're probably on the right track. Of course, it completely depends on what exactly "do stuff" does. Log(N) typically comes from algorithms which perform some kind of binary / tree-like partitioning. Here's an excellent blog post on the topic. – Daniel B Apr 9 '13 at 13:57
13  
There is no such a thing as 2N in big-O notation. – vartec Apr 9 '13 at 13:58
13  
@JörgWMittag because O(2n)=O(n) by definition of Big O – ratchet freak Apr 9 '13 at 14:01
2  
@ratchetfreak: So? They both denote the same set. By the same argument, you could say that there is no such thing as 0.5, because 0.5 = 1/2. – Jörg W Mittag Apr 9 '13 at 14:04
3  
@vartec - I don't believe JörgWMittag was purposefully trolling. In my recent research, I've noticed a lot of confusion between strict Big-O notation and "common vernacular" which mixes Big-O, Theta, and the other derivatives. I'm not saying that the common usage is correct; just that it happens a lot. – GlenH7 Apr 9 '13 at 14:16
up vote 13 down vote accepted

Formally, big-O notation describes the degree of complexity.

To calculate big-O notation:

  1. identify formula for algorithm complexity. Let's say for example two loops with another one nested inside, than another three loops not nested: 2N² + 3N
  2. remove anything except the highest term: 2N²
  3. remove all constants:

In other words two loops with another one nested inside, than another three loops not nested is O(N²)

This of course assumes that what you have in your loops are simple instructions. If you have for example sort() inside the loop, you'll have to multiply complexity of the loop by the complexity of the sort() implementation your underlying language/library is using.

share|improve this answer
    
What about the example that uses sort(). Does that not change the complexity? – Levi Hackwith Apr 9 '13 at 14:19
    
It will depend on what the "sort()" in question is. – World Engineer Apr 9 '13 at 14:23
    
sort() could be O(n!) for all we know. If it is O(NlogN), then the outer function is O(NlogN), and it's a very bad example. But presuming the sort() is O(logN), the function on the whole ignores it, because the most complex algorithm is the for loop is O(n) which clobbers the O(logN) complexity, it's not worth worrying about. If the O(logN) sort() was inside the for loop, then the whole thing would be O(NlogN). – Philip Apr 9 '13 at 14:28
    
@WorldEngineer since the code above is technically JS, let's assume that it's JS's sort algorithm / method and we'll assume that JS uses the fastest algorithm available. – Levi Hackwith Apr 9 '13 at 14:29
1  
@Philip: comparison based sorts are O(N log N), not O(log N). – kevin cline Apr 9 '13 at 19:11

If you want to analyze these algorithms you need to define //dostuff, as that can really change the outcome. Let's suppose dostuff requires a constant O(1) number of operations.

Here are some examples with this new notation:

For your first example, the linear traversal: this is correct!

O(N):

for (int i = 0; i < myArray.length; i++) {
    myArray[i] += 1;
}

Why is it linear (O(n))? As we add additional elements to the input (array) the amount of operations happening increases proportional to the number of elements we add.

So if it takes one operation to increment an integer somewhere in memory, we can model the work the loop does with f(x) = 5x = 5 additional operations. For 20 additional elements, we do 20 additional operations. A single pass of an array tends to be linear. So are algorithms like bucket sort, which are able to exploit the structure of data to do a sort in one single pass of an array.

Your second example would also be correct and looks like this:

O(N^2):

for (int i = 0; i < myArray.length; i++) {
    for (int j = 0; j < myArray.length; j++) {
        myArray[i][j] += 1;
    }
}

In this case, for every additional element in the first array, i, we have to process ALL of j. Adding 1 to i actually adds (length of j) to j. Thus, you are correct! This pattern is O(n^2), or in our example it is actually O(i * j) (or n^2 if i == j, which is often the case with matrix operations or a square data structure.

Your third example is where things change depending on dostuff; If the code is as written and do stuff is a constant, it is actually only O(n) because we have 2 passes of an array of size n, and 2n reduces to n. The loops being outside each other isn't the key factor which can produce 2^n code; here is an example of a function which is 2^n:

var fibonacci = function (n) {
    if (n == 1 || n == 2) {
        return 1;
    }

    else {
        return (fibonacci(n-2) + fibonacci(n-1));
    }
}

This function is 2^n, because each call to the function produces TWO additional calls to the function (Fibonacci). Every time we call the function, the amount of work we have to do doubles! This grows super quickly, like cutting the head off of a hydra and having two new ones sprout each time!

For your final example, if you are using an nlgn sort like merge-sort you are correct that this code will be O(nlgn). However, you can exploit the structure of the data to develop faster sorts in specific situations (such as over a known, limited range of values like from 1-100.) You are correct in thinking, however, that the highest order code dominates; so if a O(nlgn) sort is next to any operation that takes less than O(nlgn) time, the total time complexity will be O(nlgn).

In JavaScript (in Firefox at least) the default sort in Array.prototype.sort() is indeed MergeSort, so you are looking at O(nlgn) for your final scenario.

share|improve this answer

Your second example (outer loop from 0 to n, inner loop from 0 to b) would be O(nb), not O(n2). The rule is that you are computing something n times, and for each of those you are computing something else b times, thus the growth of this function depends solely on the growth of n *b.

Your third example is just O(n) -- you can remove all constants as they do not grow with n and growth is what Big-O notation is all about.

As for your last example, yes, your Big-O notation will certainly come from the sort method which will be, if it is comparison-based (as is typically the case), in it's most efficient form, O(n *logn).

share|improve this answer

Recall that this is an approximate representation of run-time. The "rule-of-thumb" is approximate because it is imprecise but gives a good first-order approximation for evaluation purposes.

The actual run-time will depend on how much heap-space, how fast is the processor, instruction set, use of prefix or post-fix increment operators, etc., yadda. Proper run-time analysis will allow determination of acceptance but having knowledge of the basics allows you to program right from the beginning.

I do agree you are on the right track to understanding how Big-O is rationalized from a textbook to a practical application. That may be the difficult hurdle to overcome.

Asymptotic growth-rate becomes important on large data sets and large programs so for typical examples you demonstrate it is not as important to proper syntax and logic.

share|improve this answer

Big oh, by definition means: for a function f(t) there exists a function c*g(t) where c is an arbitrary constant such that f(t) <= c*g(t) for t > n where n is an arbitrary constant, then f(t) exists in O(g(t)).This is a mathematical notation that is used in computer science to analyze algorithms. If your confused I would recommend lookin into closure relationships, that way you can see in a more detailed view how these algorithms get these big-oh values.

Some consequences of this definition: O(n) is actually congruent to O(2n).

Also there are many different types of sorting algorithms. The minimum Big-Oh value for a comparison sort is O(nlogn) however there is plenty of sorts with worse big-oh. For example selection sort has O(n^2). Some non comparison sort may ever have better big-oh values. A bucket sort, for example has O(n).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.