Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
11  
There is no such a thing as 2N in big-O notation. –  vartec Apr 9 '13 at 13:58
12  
@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
show 18 more comments

4 Answers 4

up vote 11 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
show 7 more comments

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

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

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

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.