What is big-O notation? How do you come up with figures like O(n)? [duplicate]

Question

Possible Duplicate:
Plain english explanation of Big O

I'd imagine this is probably something taught in classes, but as I a self-taught programmer, I've only seen it rarely.

I've gathered it is something to do with the time, and O(1) is the best, while stuff like O(n^n) is very bad, but could someone point me to a basic explanation of what it actually represents, and where these numbers come from?

Answer 1

Big O refers to the worst case run-time order. It is used to show how well an algorithm scales based on the size of the data set (n->number of items).

Since we are only concerned with the order, constant multipliers are ignored, and any terms which increase less quickly than the dominant term are also removed. Some examples:

A single operation or set of operations is O(1), since it takes some constant time (does not vary based on data set size).

A loop is O(n). Each element in the data set is looped over.

A nested loop is O(n^2). A nested nested loop is O(n^3), and onward.

Things like binary tree searching are log(n), which is more difficult to show, but at every level in the tree, the possible number of solutions is halved, so the number of levels is log(n) (provided the tree is balanced).

Something like finding the sum of a set of numbers that is closest to a given value is O(n!), since the sum of each subset needs to be calculated. This is very bad.

Answer 2

It's a way of expressing time complexity.

O(n) means for n elements in a list, it takes n computations to sort the list. Which isn't bad at all. Each increase in n increases time complexity linearly.

O(n^n) is bad, because the amount of computation required to perform a sort (or whatever you are doing) will exponentially increase as you increase n.

O(1) is the best, as it means 1 computation to perform a function, think of hash tables, looking up a value in a hash table has O(1) time complexity.