COMPSCI 220:
Algorithms and Data Structures
Yan Kolezhitskiy
Email: yan.kolezhitskiy@auckland.ac.nz
Room: 303S.569
Slides and Pictures credited to Tanya Gvozdeva
Yan Kolezhitskiy Algorithms
Running time
Running time on inputs of the same size can be very different!
For example, consider an algorithm that looks for a letter in a
word. Suppose the word has only 3 letters. Then the following
are all possibilities:
the required letter is the first letter of the word;
the required letter is the second letter of the word;
the required letter is the third letter of the word;
the required letter is not in the word;
The number of operations is different in all these
possibilities!
Yan Kolezhitskiy Algorithms
THE WORST RUNNING TIME
Pros:
This is the worst possible!
If the worst running time is reasonable, then the algorithm
might be good.
Cons:
The worst-case might be achieved on some rare artificial
examples that essentially never occur in practice.
Even if the worst running time is pretty bad it does not
necessarily mean that the algorithm/program is not
practical!
Yan Kolezhitskiy Algorithms
THE WORST RUNNING TIME
Pros:
This is the worst possible!
If the worst running time is reasonable, then the algorithm
might be good.
Cons:
The worst-case might be achieved on some rare artificial
examples that essentially never occur in practice.
Even if the worst running time is pretty bad it does not
necessarily mean that the algorithm/program is not
practical!
Yan Kolezhitskiy Algorithms
THE BEST RUNNING TIME
Pros:
Usually it is very good!
Cons:
Very often (but not always) the best running time is rather
useless because there are some rare trivial inputs for
which everything is extremely great.
Yan Kolezhitskiy Algorithms
THE BEST RUNNING TIME
Pros:
Usually it is very good!
Cons:
Very often (but not always) the best running time is rather
useless because there are some rare trivial inputs for
which everything is extremely great.
Yan Kolezhitskiy Algorithms
THE AVERAGE RUNNING TIME
Pros:
The average over all inputs
Cons:
Do you take all theoretically possible inputs?
Do you restrict yourself only to some special inputs and
exclude “artificial” inputs from consideration? If so, how
exactly do you define “artificial”?
Should you consider every input as being equally likely? If
not, what is the most “natural” distribution?
Average time analysis very often involves quite a bit of
probability and ugly sums.
Even with the simplest distributions average running time
may not be easy to compute.
Yan Kolezhitskiy Algorithms
THE AVERAGE RUNNING TIME
Pros:
The average over all inputs
Cons:
Do you take all theoretically possible inputs?
Do you restrict yourself only to some special inputs and
exclude “artificial” inputs from consideration? If so, how
exactly do you define “artificial”?
Should you consider every input as being equally likely? If
not, what is the most “natural” distribution?
Average time analysis very often involves quite a bit of
probability and ugly sums.
Even with the simplest distributions average running time
may not be easy to compute.
Yan Kolezhitskiy Algorithms
THE AVERAGE RUNNING TIME
In these course we will usually consider all possible inputs and
will view them as equally likely
Yan Kolezhitskiy Algorithms
The best/worst/average running time should be defined for any
valid input n!
Yan Kolezhitskiy Algorithms