Classification of Algorithms How many different combinations can sequence of digits have?

No. of digits No of combinations

Comparing Algorithms 2 2 Exponential Time O(2n)

3 6 The time taken for the algorithm will

• The time efficiency of algorithms refers how long an algorithm takes to run as
a function of the size of the input. 4 24 grow as the power of the number of
• More than one algorithm can be used to solve the same proble. inputs, so the time taken for the
5 120 algorithm to run will grow very quickly
• For instance to calculate the sum of a sequence of numbers we can use the
following algorithm: as more input data are added.
𝑠𝑢𝑚 = (𝑛 + 1) ∗ 𝑛 / 2 Big O notation gives us an idea of how long a program will run if we increase the
where 𝑛 is the number we wish to sum the values up to. Using this calculation the size of the input. We need to consider how many operations will need to be
time remains constant regardless the value of n. In other words, regardless of how carried out for a given size of input. This gives us the time complexity of the
many numbers we wish to add up the time taken will always be same. algorithm.
The time taken for an algorithm to run will depend on the hardware (eg processor
clock speed, RAM size), even though the number of operations will be constant for
We could use an alternative algorithm to calculate the sum of a sequence of Constant Time O(1)
a fixed input.
numbers
The time remains constant even when
Tractable problems are problems that have a polynomial or less time solution eg
sum ← 0 the number of input increases. E.g.
O(1), O(n), O(log n), O(n2)
FOR i ← 1 to n calculating the sum of a sequence of
sum ← sum + i numbers.
ENDFOR Intractable problem are problems that can be theoretically solved but take longer
OUTPUT sum than polynomial time e.g. O(n!), O(2n)
𝑠𝑢𝑚 = (𝑛 + 1) ∗ 𝑛 / 2

Using this algorithm the number of operations increases in linear time with the Heuristic algorithms are used to provide approximate but not exact solutions to
Regardless of how many numbers we
size of the input. Therefore, the time taken for the algorithm to run will grow in intractable problems
wish to add up the time taken will
linear time as in size of the input increases. Clearly this is more inefficient than the always be same.
first algorithm even though it solves the same problem. The travelling Salesman Problem
The idea is to find the shortest route to visit all cities. This is a permutation of the
Another area where algorithms differ in their efficiency is in regard to the memory number of cities so has a factorial time complexity so quickly becomes an
Logarithmic Time O(log n) intractable problem with an unfeasibly huge number of permutations.
requirements of algorithms. For instance programs that read in huge data files into
memory can end up taking up a large space in memory. The time taken for the algorithm to To solve this we use an heuristic algorithm. This provide an acceptable solution to
run will grow slowly as in size of the the problem but it may not be the optimal or best solution. So for the travelling
When developing algorithms it is important to consider the hardware constraints input increases.
of the system you are developing for (eg mobile phone which has limited salesman problem we may find a short route but not necessarily the shortest
processing and space capability). If you have large memory then your algorithm route. Heuristic algorithms for the travelling salesman problem include the
can afford to be less space efficient. Likewise if you have access to tremendous following:
processing power algorithm (eg supercomputer) your may not need to be time
efficient although it is still desirable to make algorithms as efficient as possible. • Greedy algorithm – take the shortest route to the next city
• Visit the cities in a circle
Maths for Big-O Notation Linear Time O(n) • Brute force algorithm – Apply to small but different subsets of cities and
combine together. Apply the brute force algorithm to fewer manageable
A function allows us to map a set of input values to a set output values The time taken for the algorithm to problems rather than a single intractable problem
run will grow in linear time as in size
𝑦 = 𝑓(𝑥) of the input increases. Time Complexity of common algorithms
Eg inefficient algorithm to calculate Linear Search O(n)
where x is a value from the domain and y a value from the codomain the sum of a sequence of numbers Binary Search O(log n)
Binary Tree Search O(log n)
domain -> codomain sum = 0 Bubble Sort O(n2)
for i=0 to n Merge sort O(n log n)
A linear function takes the form 𝑦 = 𝑚𝑥 + 𝑐, where m is the gradient and c the sum = sum + i
Travelling Salesman Problem O(n!)
intercept on the y axis. output(sum)
Brute force password cracker where n is the length O(An)
of the password
A polynomial function takes the form 𝑦 = 𝑎𝑥 2 + 𝑏𝑥 + 𝑐
Polynomial Time O(n2)
Unsolvable problems Some problems cannot be solved by a computer. The
An exponential function takes the form 𝑦 = 𝑎 𝑥 Halting problem is one such problem and show that some problems cannot be
The time taken for the algorithm to
solved algorithmically.
A logarithmic function takes the form 𝑦 = 𝑎 log 𝑛 𝑥 run will grow proportionally to the
square of the size of the data set.
The halting problem states that there is no computer program that exists that can
Permutations illustrate how the number of operations grows factorially when we Normally when you have nested for
determine whether another computer program will halt or will continue to run
add additional dimensions to some problems. loops this will have a polynomial time
forever given some specified input.
complexity.
The halting problem show that some problems cannot be solved by a computer
for i=0 to n
for j=0 to n
Do something