Comparing algorithms

We will consider two ways of comparing algorithms: time complexity and space complexity. Time complexity is the time it will take for an algorithm to execute. Space complexity is the amount of memory required during the execution of the algorithm.

Time complexity

Time complexity can be expressed as a function based on the relative size of the problem i.e. for a search or sort it means the size of the array being searched or sorted. Some of the types of function that may be expressed are: Constant; Linear; Polynomial; Exponential; Logarithmic

Constant time

An algorithm with constant time will always take the same amount of time to execute.

Linear time

Linear functions are generally expressed in the form:
f(x) = ax + b
As the value of x increases, the relative value of the constant, b, added to the first term is less and less relevant.
f(x) = 2x + 3
f(10) = 2 x 10 + 3 = 23
f(100,000) = 2 x 100,000 + 3 = 200,003

Polynomial time

Polynomial functions are generally expressed in the form:
f(x) = ax² + bx + c
As the value of x increases, the relative value of the bx and the constant, c, added to the first term are less and less relevant.
f(x) = 2x² + 3x + 8
f(10) = 2 x 10² + 3 x 10 + 8 = 238
f(100,000) = 2 x 100,000² + 3 x 100,000 + 8 = 20,000,300,008

Exponential time

Exponential functions are expressed in the form:
f(x) = ab^x
Exponential functions become very large very quickly as the size of x grows.
f(x) = 2^x
f(10) = 2¹⁰ = 1024 f(100,000) = 2^100,000 = approaching infinity (30,103 digits).

Another type of exponential function is of the form:
f(x) = x!.
x! means x factorial.
f(5) = 5! = 5 x 4 x 3 x 2 x 1 = 120

Logarithmic time

Logarithmic functions take the form of:
f(x) = a log_nx
The log of a number is the power you would have to raise the base to in order to reach it.
f(x) = log₂x
f(10) = log₂10 = 3.322
f(100,000) = log₂100,000 = 16.61

Big O Notation

Big O notation is used as a quick way of describing the time complexity of an algorithm.

Big O	Time Complexity	Description/example
O(1)	Constant time	Calculating the length of an array takes constant time because the array will be implemented with pointers and the length will be the rear pointer + 1 in a zero indexed array language.
O(n)	Linear time	A linear search has a linear worst time because the larger the list becomes the more searches are performed to not find an item.
O(n²)	Polynomial time	Because it has a set of nested loops that each execute n times the bubble sort has polynomial time complexity.
O2ⁿ	Exponential time	A recursive function that performed two operations each time it did not reach its stopping condition would have exponential time.
O(log n)	Logarithmic time	A binary search which splits the list in half each time has logarithmic time.
O(n!)	Exponential(factorial) time	Calculating all the possible seating arrangements at a wedding would have factorial time complexity.

Knowledge check

Questions:

Correct:

Question text