31

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?

Levi Hackwith
  • 843
  • 1
  • 7
  • 13
  • 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](http://www.infoarena.ro/blog/numbers-everyone-should-know) post on the topic. – Daniel B Apr 09 '13 at 13:57
  • Side note: I could not figure out how to make the NLogN work with the right LaTex commands. If someone wants to change that, feel free. – Levi Hackwith Apr 09 '13 at 13:58
  • 15
    There is no such a thing as `2N` in big-O notation. – vartec Apr 09 '13 at 13:58
  • @vartec And that's because when calculating big O notation you remove all the constants, right? – Levi Hackwith Apr 09 '13 at 13:59
  • 1
    @vartec: Of course, there is. Why wouldn't there be? – Jörg W Mittag Apr 09 '13 at 13:59
  • 15
    @JörgWMittag because O(2n)=O(n) by definition of Big O – ratchet freak Apr 09 '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 09 '13 at 14:04
  • 3
    @JörgWMittag: this really isn't the place for trolling. – vartec Apr 09 '13 at 14:09
  • @JörgWMittag - I believe that 2N instead of just N is allowed as part of Theta notation, which is a derivative (or subset?) of Big-O notation. https://en.wikibooks.org/wiki/Data_Structures/Asymptotic_Notation#Big-O_Notation –  Apr 09 '13 at 14:14
  • 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. –  Apr 09 '13 at 14:16
  • 1
    @GlenH7: Exactly. I would simply like to know, where *exactly* in the definition of the Bachmann-Landau notation it says that O(2n) is not allowed. I must admit that haven't *thoroughly* read the *original* 1894 and 1909 papers by Bachmann and Landau, but I *have* at least skimmed them, and I couldn't find anything that supports that claim. – Jörg W Mittag Apr 09 '13 at 14:28
  • 2
    @JörgWMittag - vartec points it out in his answer below. AFAIK, strict Big-O drops scalar values (constants) in the reduction step since the constants have less and less effect as N goes towards infinity. When N is a google, the additional effect of multiplying by 2 or 3 becomes effectively nil; so it's dropped in order to make the comparison more clear. N vs N or N vs 2N isn't an interesting Big-O comparison whereas N vs N*N is interesting. But I'm NOT an expert on notation, so take my explanation with a healthy degree of skepticism. –  Apr 09 '13 at 14:36
  • 1
    O(2 N) is perfectly fine. It doesn't take a mathematician to see that it is well-defined and equal to O(N) - the analogy with 0.5 and 1/2 above is dead on. The only question is whether it is useful to write it out instead of automatically simplifying to (N). And I'd say it helps more than it hurts: It also tells the reader that there's a factor of 2 in the actual value, and that it's significant (e.g. that the algorithm consists of two O(N) operations from a high level view). It can make intent clearer, and the worst that can happen is that you have to remind beginners that O(2 N) = O(N). –  Apr 09 '13 at 15:09
  • 1
    @GlenH7: *Θ(f(N))* means that your function is both *O(f(N))* (upper bounds) and *o(f(N))* (lower bounds). In all three cases it's asymptotic bounds, constants are irrelevant. – vartec Apr 09 '13 at 15:37
  • Technically speaking, the sample for O(n**2) is incorrect; it's either O(infinity) if i <= b or O(n) otherwise. :-) Assuming it's meant to be `c <= b` as the for-condition, I'm not sure how to calculate the Big-O of a function with 2 independent variables. For a proper O(n**2) function, you need the inner loop's condition to be `c <= n` (or some other f(n), like n/2 or sqrt(n) ) as well. – Hellion Apr 09 '13 at 16:28
  • 2
    Since they are independent variables, we would define the inner loop as O(n) and the outer loop as O(m). As such, I thought the overall function's notation should be O(n * m), but feel free to correct me if I am mistaken. – Dan Lyons Apr 09 '13 at 17:12
  • 2
    Whether O(2N) is valid or not from a mathematical viewpoint, it will certainly get you an incorrect answer on a test asking for what Big-O is this in a computer science class. Also, just from common usage it is simple to tell that 2n is wrong...I've never seen O(2.345n^2) or anything remotely similar. A more common occurence might be O(n^2/2), where the constant would be 1/2, but you don't see that used either. Most likely, because that is not the intended usage of Big-O in computer science. – Dunk Apr 09 '13 at 17:59
  • @GlenH7 I think you mean googol, not google. https://en.wikipedia.org/wiki/Googol (I'm also thrilled to see that word be used outside academia) – CamelBlues Apr 09 '13 at 18:17
  • @CamelBlues - you are correct, I meant a googol, not the search engine. –  Apr 09 '13 at 18:32
  • The second case is not O(n^2), it's O(n*b). The third case is not O(2N) or O(N), it's O(n + b). – kevin cline Apr 09 '13 at 19:10
  • **Please avoid extended discussions in the comment section. If you would like to continue this conversation then I encourage you to visit [The Whiteboard](http://chat.stackexchange.com/rooms/21/the-whiteboard) chat room. Thank you.** – maple_shaft Apr 09 '13 at 19:43
  • @DanLyons You would be correct if the inner loop was sane ;) – Izkata Apr 09 '13 at 20:37
  • @JörgWMittag If O(2n) is a thing, then it's reasonably a bigger thing than O(n). But it is easy to create a single loop (O(n)) which nonetheless runs slower than two individual loops (O(2n)) for any n. Thus, O(2n) makes no sense. – Jacob Raihle Jan 07 '19 at 15:57
  • @JacobRaihle: Well, I maintain that, yes, O(2n) *is* a thing, but it's not "reasonably a bigger thing than O(n)". In fact, it is easy to show that the set of functions described by O(2n) is in fact the same set as the set of functions described by O(n). – Jörg W Mittag Jan 08 '19 at 14:17
  • @JörgWMittag the unsaid alternative is that if O(2n) is *not* larger than O(n), then it is at best pointless. – Jacob Raihle Jan 08 '19 at 15:14

5 Answers5

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.

vartec
  • 20,760
  • 1
  • 52
  • 98
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.

Bryce Danz
  • 71
  • 1
  • 2
  • 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 07 '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.

Mushy
  • 345
  • 1
  • 7
-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).