Where to find what O(n^2) and O(n) etc means?

Question

I've been noticing answers on stack overflow that use terms like these, but I don't know what they mean. What are they called and is there a good resource that can explain them in simple terms?

Answer 1

That notation is called Big O notation, and is used as a shorthand to express algorithmic complexity (basically how long a given algorithim will take to run as the input size (n) grows)

Generally speaking, you'll run into the following major types of algorithims:

1. O(1) - Constant - The length of time that this algorithim takes to complete is not dependent on the number of items that the algorithim has to process.
2. O(log n) - Logarithmic - The length of time that this algorithim takes to complete is dependent on the number of items that the algorithim has to process. As the input size becomes larger, less time is needed for each new input.
3. O(n) - Linear - The length of time that this algorithim takes to complete is directly dependent on the number of items that the algorithim has to process. As input size grows, the time it takes grows in equal amounts.
4. O(n^2) - Polynominal - As input size grows, the time it takes to process the input grows by a larger and larger amount - meaning that large input sizes become prohibitively difficult to solve.
5. O(2^n) - Exponential - The most complicated types of problems. Time to process increases based on input size to an extreme degree.

Generally you can get a rough gauge of the complexity of an algorithim by looking at how it's used. For example, looking at the following method:

function sum(int[] x) {
    int sum = 0;
    for (int i = 0; i < x.length; i++) {
        sum += x[i];
    } 
    return sum;
}

There's a few things that have to be done here:

• Initialize a variable called sum
• Initialize a variable called i
• For each iteration of i: Add x[i] to sum, add 1 to i, check if i is less than x.length
• Return sum

There's a few operations that run in constant time here (the first two and the last), since the size of x wouldn't affect how long they take to run. As well, there are some operations that run in linear time (since they are run once for each entry in x). With Big O notation, the algorithim is simplified to the most complex, so this sum algorithim would run in O(n)