# Time complexity explained

What is the running time of the following algorithm?

Algorithmmax(arr): max ← arr[0]fori = 1tolen(arr)-1ifarr[i] > max max ← arr[i]returnmax

The answer depends on factors such as input, programming language and runtime, coding skill, compiler, operating system, and hardware.

We often want to reason about **execution time** in a way that depends
only on the **algorithm** and its **input**.
This can be achieved by choosing an **elementary operation**,
which the algorithm performs repeatedly, and define
the **time complexity** T(*n*) as the number of such operations
the algorithm performs given an array of length *n*.

For the algorithm above we can choose the comparison
`arr[i] > max`

as an elementary operation.

- This captures the running time of the algorithm well, since comparisons dominate all other operations in this particular algorithm.
- Also, the time to perform a comparison is constant:
it doesn’t depend on the size of
`arr`

.

The time complexity, measured in the number of comparisons,
then becomes T(*n*) = *n* - 1.

In general, an **elementary operation** must have two properties:

- There can’t be any other operations that are performed more frequently as the size of the input grows.
- The time to execute an elementary operation must be constant: it mustn’t increase as the size of the input grows.

## Worst-case time

Consider this algorithm:

Algorithmcontains(arr, x):fori = 0tolen(arr)-1ifx == arr[i]returntruereturnfalse

The comparison `x == arr[i]`

can be used as an elementary operation in this case.
However, for this algorithm the number of comparisons depends not only on the number of elements, *n*, in the array but also on the value of `x`

and the values in `arr`

:

- If
`x`

isn’t found in`arr`

the algorithm makes*n*comparisons, - but if
`x`

equals`arr[0]`

there is only one comparison.

Because of this, we often choose to study **worst-case** time complexity:

- Let T
_{1}(*n*), T_{2}(*n*), … be the execution times for all possible inputs of size*n*. - The worst-cast time complexity W(
*n*) is then defined as W(*n*) = max(T_{1}(*n*), T_{2}(*n*), …).

The worst-cast time complexity for the `contains`

algorithm thus becomes
W(*n*) = *n*.

Worst-case time complexity gives an upper bound on time requirements and is often easy to compute. The drawback is that it’s often overly pessimistic.

## Average-case time

**Average-case** time complexity is a less common measure:

- Let T
_{1}(*n*), T_{2}(*n*), … be the execution times for all possible inputs of size*n*,

and let P_{1}(*n*), P_{2}(*n*), … be the probabilities of these inputs. - The average-case time complexity is then defined as
P
_{1}(*n*)T_{1}(*n*) + P_{2}(*n*)T_{2}(*n*) + …

Average-case time is often harder to compute, and it also requires knowledge of how the input is distributed.

## Linear vs. quadratic time

Finally, we’ll look at an algorithm with poor time complexity.

Algorithmreverse(arr):fori = 1tolen(arr)-1 x ← arr[i]forj = idownto1 arr[j] ← arr[j-1] arr[0] ← x

We choose the assignment `arr[j] ← arr[j-1]`

as elementary operation.
Updating an element in an array is a constant-time operation,
and the assignment dominates the cost of the algorithm.

The number of elementary operations only depends on *n*
in this case, and the time complexity becomes

W(*n*) =
1 + 2 + … + *n* - 1 =
*n*(*n* - 1)/2 =
*n ^{2}*/2 -

*n*/2.

The quadratic term dominates for large *n*,
and we therefore say that this algorithm has **quadratic** time complexity.
This means that the algorithm **scales poorly** and can be used **only for small input**:
to reverse the elements of an array with 10,000 elements,
the algorithm will perform about 50,000,000 assignments.

In this case it’s easy to find an algorithm with **linear** time complexity.

Algorithmreverse(arr):fori = 0ton/2 swap arr[i] and arr[n-i-1]

This is a **huge improvement** over the previous algorithm:
an array with 10,000 elements can now be reversed
with only 5,000 swaps, i.e. 10,000 assignments.
That’s roughly a 5,000-fold speed improvement,
and the improvement keeps growing as the the input gets larger.

It’s common to use **Big O notation**
when talking about time complexity. We could then say that
the time complexity of the first algorithm is Θ(*n*^{2}),
and that the improved algorithm has Θ(*n*) time complexity.

## Comments