CSC 378: Data Structures and Algorithm Analysis
How to analyze with O()
for i = 1 to
while (condition)
No fixed rule: must analyze to find a bound on the number of iterations.
If
then
else
e.g.
Recall that is a set of functions. Rules VI, VII, and VIII are provable if we consider and to act on all pairs from the two sets. For example: .
In this situation, can be replaced by .
Note that the symbol is the convention here, since the left-hand-side of the last equation is not mathematically meaningful.