30

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?

  • 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
  • 15
    There is no such a thing as 2N in big-O notation. – vartec Apr 9 '13 at 13:58
  • 15
    @JörgWMittag because O(2n)=O(n) by definition of Big O – ratchet freak Apr 9 '13 at 14:01
  • 3
    @JörgWMittag: this really isn't the place for trolling. – vartec Apr 9 '13 at 14:09
  • 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. – user53019 Apr 9 '13 at 14:16
27

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, then another three loops not nested: 2N² + 3N
  2. remove everything except the highest term: 2N²
  3. remove all constants:

In other words two loops with another one nested inside, then 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.

  • Strictly speaking "remove all constants" would turn 2N³ into N. "remove all additive and multiplicative constants" would be closer to the truth. – Joachim Sauer Apr 9 '13 at 21:12
  • @JoachimSauer: N² = N*N, there is no constant there. – vartec Apr 10 '13 at 8:41
  • @vartec: according to the same argument 2N = N+N. – Joachim Sauer Apr 10 '13 at 11:12
  • 2
    @JoachimSauer, your "strictly speaking" as absolutely non-conventional. See en.wikipedia.org/wiki/Constant_(mathematics). When talking about polynomials, "constant" always refers only to coefficients, not to exponents. – Ben Lee Apr 15 '13 at 20:58
  • 1
    @vartec, see my comment above. Your use of "constant" here was absolutely correct and conventional. – Ben Lee Apr 15 '13 at 20:59
7

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.

  • Is your Fibonacci example actually Fibonacci? I know this doesn't argue against the point you were trying to make, but the name might be misleading to others and therefore be distracting if it isn't actually Fibonacci. – Paul Nikonowicz Jan 7 '17 at 21:57
1

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

0

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.

-1

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

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