Two areas are important for performance:
There are some circumstances where the space/memory used must be analyzed. For example, for large quantities of data or for embedded systems programming.
Components of space/memory use:
1. instruction space | Affected by: the compiler, compiler options, target computer (cpu) |
2. data space | Affected by: the data size/dynamically allocated memory, static program variables, |
3. run-time stack space | Affected by: the compiler, run-time function calls and recursion, local variables, parameters |
The space requirement has fixed/static/compile time and a variable/dynamic/runtime components. Fixed components are the machine language instructions and static variables. Variable components are the runtime stack usage and dynamically allocated memory usage.
One circumstance to be aware of is, does the approach require the data to be duplicated in memory (as does merge sort). If so we have 2N memory use.
Space efficiency is something we will try to maintain a general awareness of.
Clearly the more quickly a program/function accomplishes its task the better.
The actual running time depends on many factors:
When analyzing for time complexity we can take two approaches:
For any time complexity consideration there are 3 cases:
Usually worst case is considered since it gives an upper bound on the performance that can be expected. Additionally, the average case is usually harder to determine (its usually more data dependent), and is often the same as the worst case. Under some circumstances it may be necessary to analyze all 3 cases (algorithms topic).
Order of magnitude/asymptotic categorization eliminates hardware from consideration and expresses efficiency in terms of data size, N.
There are several definitions which all work in a similar manner. Also there are some Greek letters involved which are unrepresentable in HTML at this point and so are spelled out.
Order of magnitude/asymptotic categorization ignores coefficients and is based on larger values of N and so if coefficients are large or values of N are small the behavior may be different from expected.
Since the higher order term dominates the lower order terms in an algebraic expression for large N, the low order terms can be ignored. Thus the following functions are be used.
Function | Big-O | Name |
---|---|---|
1 | O(1) | constant |
log n | O(log n) | logarithmic |
n | O(n) | linear |
n log n | O(n log n) | n log n |
n2 | O(n2) | quadratic |
n3 | O(n3) | cubic |
2n | O(2n) | exponential |
n! | O(n!) | factorial |
Example:
5n + 7 <= 5n + n for n >= 7 <= 6n
So
c = 6
and
n0 = 7
thus
5n + 7
is
O(n).
Example:
3n2 + 4n <= 3n2 + n2 for n >= 4 <= 4n2
So
c = 4
and
n0 = 4
thus
3n2 + 4n
is
O(n2).
It is usually assumed the bound is tight. For example, 3n + 4 function is bounded by n2 for n > 4 and so is O(n2). This is not a tight bound however, 3n + 4 is O(n).