We can consider the average case or the worst case performance (refering to an instance of a given problem).
Usually we treat only the worst case performance:
The worst case occurs fairly often,
example: looking for in entry in a database that is
not present.
The result of the worst case analysis
is often not different to the average case analysis
(same order of complexity).
One way to compare running times is simply to run several tests for each algorithm and compare the timings.
Another way is to estimate the time required for an algorithm to solve a problem.
The result of the analysis of an algorithm is usually a formula giving the amount of machine operations (e.g., floating point operations, number of memory accesses, number of comparisons, etc ) or some other metric (e.g., number of elements to sort, neurons or connections in a neural network, vertices or edges in a tree, etc. ), that the algorithm takes to complete.
In the following we write running times as a function of n.
Thus, when comparing the running times of two algorithms:
Constant factors can be ignored.
Lower order terms are unimportant
when the higher order terms are different.
For instance, when we
analyze selection sort, we find that it takes
T(n) = n2 + 3n - 4
array accesses.
For large values of n, the 3n - 4 part is
insignificant compared to the n2 part.
An algorithm that takes a time of 100n2 will still be faster
than an
algorithm that n3 for any value of n larger than 100.
0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) for all n ≥ n0 .
In other words: For large inputs (asymptotically) f(n) is "sandwiched" between c1 g(n) and c2 g(n) .
Examples:
2n2+3n is θ(n2).
2n3+3n is not θ(n2).
0 ≤ f(n) ≤ c g(n) for all n ≥ n0 .
In other words: For large inputs (asymptotically) f(n) is below c g(n):
Examples:
3n-6 is O(n).
9n4+12n2+1234 is O(n4).
n+log(n) is O(n).
log(n)+5log(log(n)) is O(log(n)).
1234554321 is O(1).
3/n is O(1/n).
0 ≤ c g(n) ≤ f(n) for all n ≥ n0 .
In other words: For large inputs (asymptotically) f(n) is above c g(n) .
Note:
We have f(n) = Θ(g(n))
iff (if and only if)
f(n) = O(g(n))
and
f(n) = Ω(g(n)).
In other words:
If f(n) is Θ(g(n)), the f(n) is Ω(g(n)).
If f(n) is Θ(g(n)), then f(n) is O(g(n)).
Example:
2n3+3n is Ω(n3).
0 ≤ f(n) ≤ c g(n) for all n ≥ n0 .
In other words:
The inequality holds for all constants c.
For any constant c
we can come up with large enough inputs n
so that f(n)
is below
c
g(n)
.
g(n) grows a lot faster than f(n) : f(n)/g(n)→0 as n→∞.
Example:
log(n) is o(n)
0 ≤ c g(n) ≤ f(n) for all n ≥ n0 .
As an alternative definition we can say the following.
Definition: Let f(n) and g(n) be real valued functions of an integer variable. We say f(n) is ω(g(n)) if g(n) is o(f(n)). This is pronounced as "f(n) is little-omega of g(n)".
f(n) grows a lot faster than f(n) : f(n)/g(n)→∞ as n→∞.
Example:
n2 is ω(nlog(n)).
If a program takes a lot of time,
you can still run it, and just wait longer for the result.
However if
a program takes a lot of memory, you may not be able to run it at all,
so this is an important parameter to understand.
We analyze things differently for recursive and iterative programs.
For an iterative program,
it is usually just a matter of
looking at the variable declarations
and storage allocation calls, e.g., array of n numbers.
Analysis of recursive program
space is more complicated:
the space used at any time is the total space used by all
recursive calls active at that time.
Each recursive call takes a constant amount of space: some space for local variables and function arguments, and also some space for remembering where each call should return to.