CSC 378: Data Structures and Algorithm Analysis

INTRODUCTION TO COMPLEXITY ANALYSIS

Time Complexity

What is the number of "basic steps" taken by an algorithm, as a function of the size of its input?

time complexity    input size    number of basic steps

"Input size" can be defined in terms of the number of bits, nodes, elements, integers, and so on.

A "step" is an operation that takes constant time, such as a variable assignment, a comparison, an array access, an arithmetic function, and so on.

Model of Computation

To simplify our investigations, we will use the "unit cost random access machine", or RAM. Other models include Turing Machines, PRAMs, and integrated circuits.

In a RAM, we can access unlimited memory (i.e. arrays) in one step, and can perform arithmetic on arbitrarily large numbers in one step.

For example, consider:

In the RAM model, this code has a time complexity of

index1.gif

where index2.gif is the floor of the log, rounded down, as in the folowing table:

Asymptotic Complexity

"Asymptotic" means "in the limit".

Asymptotic complexity describes the running time of an algorithm as the input size gets very large. By comparing the asymptotic complexities of two algorithms, we can determine which will be better when the size of the input gets past a certain point.

Let's say that we have two algorithms that solve a certain problem:

Algorithm A takes time index3.gif steps and
Algorithm B takes time index4.gif steps.

Q: When is index5.gif ?
A: When index6.gif or, in other words, when index7.gif .

This can be expressed graphically:

index8.gif

Another example -

index9.gif
index10.gif

So index11.gif
iff index12.gif
iff index13.gif
iff index14.gif .

Q: At what point is index15.gif big enough so that this is true?
A: When index16.gif !

The "dominant term" of index17.gif is index18.gif .
The "dominant term" of index19.gif is index20.gif .

As index21.gif gets large enough, the dominant term has a much larger effect on the running time than the other terms. So perhaps we can ignore the smaller terms and only compare the dominant terms. That would be much simpler.

If algorithm A has a "larger" dominant term than algorithm B then A will, once index22.gif gets large enough, take more time than B.

Informal O()

index23.gif is "big-oh" notation. It is used to capture the idea of a dominant term.

index24.gif is spoken as "big-oh of index25.gif ".

Let index26.gif be a set of functions.  Then index27.gif is (intuitively) the set of functions whose dominant term is at most index28.gif . It can also include functions whose dominant term is less than index29.gif .

For example:

index30.gif index31.gif index32.gif
index33.gif index34.gif index35.gif

But also -

index36.gif index37.gif index38.gif
index39.gif index40.gif index41.gif
index42.gif index43.gif index44.gif

index45.gif is the set of functions whose dominant term is a constant.

index46.gif index47.gif index48.gif since index49.gif
index50.gif index51.gif index52.gif
index53.gif index54.gif index55.gif since index56.gif



Back to the lecture index

Copyright 1998     James Stewart