Valhalla Legends Archive

I have been reading about Big O Notation, and just want to make sure I understand it correctly.

Now for example we will use a Linear Big O Notation O(N). If N = 1,000,000 and the constant time for one iteration of the algorithm is 10ms on a specific computer, that would mean that the overall time required for the algorithm to complete would be 10,000,000ms correct?

Using a Quadratic Big O Notation O(N^2) with the same n and constant time, the overall time for the algorithm to complete would be 40,000,000ms?

I am still working on figuring out Logarithms, so I will post some questions about Logarithmic Big O Notations later.

I know that the Big O Notation represents the efficiency of the algorithm, which could also be memory usage, disk usage, network usage, etc, and that it is system/compiler dependent because the performance constants will change. I just want to make sure that I understand how to use it to correctly figure out what the efficiency of the algorithm is if the performance constants are known.

O(Log2 N)
N = 1,000,000
C(Time) = 10ms

Log2 1,000,000 = 6

So would the overall time required to run this algorithm be 60ms?

I don't think Big O Notation is meant to be used that way, with the constants. At least not in the general mathematic case.

O actually stands for Order - the theory/notation is Orders of Complexity. An O() expression does not represent actual time, it represents the relationship between the time something takes and the the size of the task. Generally, this equates to n being the number of items in a set, or the number of bits in a mathematical function, or similar.

Thus, O(n) means that the algorithm will take proportionally longer for each item in the set. A set of one item would take 1 unit of time (one unit of time could be any constant measurement - perhaps the time the task takes when n=1), 2 would take 2 units, 3 would take 3 units, and soforth. O(n^2), however, means that item one will take 1^2=1 unit of time, 2 would be 2^2=4 units, 3 would be 3^2=9 units, and soforth. These are polynomial, or tractable algorithms. A example of a really bad  algorithm (or just an algorithm for an intractable problem) might be something like O(n!) or O(2^n), which is exponential, and thus not solvable in a reasonable amount of time.

Working out the O() for your own algorithm can be quite tricky. A good start is to note how many actions you must take for each item in your algorithm (whatever that may be). An action could be a comparison, a swap, an assignment, etc. Try to boil down the numbers you get into an equation that represents the number of actions taken for a particular value of n. That should be close or equal to your O() for the algorithm.

Quote from: Arta[vL] on June 18, 2004, 08:32 PMThus, O(n) means that the algorithm will take proportionally longer for each item in the set. A set of one item would take 1 unit of time (one unit of time could be any constant measurement - perhaps the time the task takes when n=1), 2 would take 2 units, 3 would take 3 units, and soforth. O(n^2), however, means that item one will take 1^2=1 unit of time, 2 would be 2^2=4 units, 3 would be 3^2=9 units, and soforth. These are polynomial, or tractable algorithms. A example of a really bad  algorithm (or just an algorithm for an intractable problem) might be something like O(n!) or O(2^n), which is exponential, and thus not solvable in a reasonable amount of time.

So if that unit of time was 10ms on my system, I would be correct as far as how long it would take the algorithm to complete on my system then, correct?

No.

Big O notation means "not asymptotically greater than".

If your algorithm is O(f(n)), then there is some constant c, such that for almost all n, your algorithm takes less than c*f(n) steps.

For example if your algorithm takes 8n + 4 steps, it is O(n).
If it takes 9n^2 - n + 5 steps, it is O(n^2).

It doesn't tell you how fast the algorithm is generally.
It tells you how fast the algorithm is expected to be on very big inputs.

O(1) means the algorithm takes constant time, regardless of input size.

Again, you can't use the asymptotic notation to calculate exactly how long it takes an algorithm to finish. You can however calculate the "order" of length it would take.

Example:
An insertion sort sorts an array in O(n^2) worst time complexity.
A heap sort sorts an array in O(n lg(n)) worst time complexity.

For n = 1000, the insertion sort would take "an order of" 1000000 steps in the worst case (this could be 1500000 or 2000000 or something like that, too!), and the heap sort would take "an order of" ~10000 steps in the worst case (again, this is not an exact number, but an "order").

Already for an input of size 1000, the heap sort is expected to perform about 100 times better than the insertion sort. For bigger inputs, you'll get even bigger differences in performance.

On the other hand, this is only an analysis of the "worst case" for both algorithms, i.e. the case where they have to perform a maximum number of operations. On other cases, such as the "average case" or the "best case", it might not be so.

The "best case" of the insertion sort is to get an array that is already sorted. Then, it makes one pass through the array, and will only take O(n) steps.
Heap sorting the same array would still mix & match the elements, and would take O(n lg n) steps.
(I'm not sure what the best case of heap sort would be.)

Heap sort is still way better than insertion sort, because the best case rarely happens, and O(n lg n) is much better than O(n^2).

Ahhh, that makes much more sense, now I need to start figuring out how to find the order of complexity for my own algorithms. Thanks for the help! More questions will come.