Is this a Proper "Rule" for Identifying the "Big O" Notation of an Algorithm?

Question

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: N²

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?

Answer 1

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: N²

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.

Answer 2

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.

Answer 3

Your second example (outer loop from 0 to n, inner loop from 0 to b) would be O(nb), not O(n²). 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).

Answer 4

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.

Answer 5

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