Time complexity

Page 1

Complexity

A linear search: very simple algorithmically, requires little extra data to run, takes a long time to work through all the values if there is a lot of data to work with, each step only eliminates a single value

A binary search: a more complicated algorithm, more steps, requires more memory space, is much faster to execute, the input size halves each step

time complexity - how the time taken is effected by the size of the input

Big O Notation

in worst case scenario what is the longest time taken. this describes how the run time increases as a function of the input

O(1) constant time complexity

if the run time is not affected by the size of the input.

Example: Getting the first element of an array.

It doesn’t matter how big the array is, it only takes one step to get the first element.

not effected by linear or binary search

Page 2

O(n)

if its run time increases linearly with the size of its input.

if the input doubles, the run time doubles.

Example: Linear Search

Since the algorithm has to check every item in the list, if the list size doubles, the number of steps doubles.

O(n^2)

The run time of an algorithm increases with the square of the input size.

This happens in algorithms with nested loops.

Example: Checking an array for duplicates.

Since each number has to be checked with each other number, an increase of 1 number results in every number having to be checked again.

O(2^n)

These algorithms double in run time for each increase of the input size.

Some recursive algorithms are O(2n)

Page 3

O(n!)

The run time increases with the factorial of the input. These algorithms become very slow very quickly.

Brute force route-finding algorithms can be O(n!)

O(log(n))

intractable- means not solve able within a reasonable amount of time