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

       

"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.

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

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

"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 steps and
Algorithm B takes time steps.

Q: When is ?
A: When or, in other words, when .

This can be expressed graphically:

Another example -

So
iff
iff
iff .

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

The "dominant term" of is .
The "dominant term" of is .

As 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 gets large enough, take more time than B.

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

is spoken as "big-oh of ".

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

For example:

But also -

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