Unit 12 Algorithms

A process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer

• Binary search • Insertion Sort • Bubble Sort

• Routing problems • Timetabling aircrafts • Searching information on the Internet • Encrypting communications • Sorting large amounts of data • Writing a compiler program

• Has clear and well stated steps • Should allow for invalid inputs • Must terminate at some point • Should be executed efficiently and in as few steps as possible • Must be easy to understand and modify by other people

The number of assignment statements

A function that takes the form of f(n) = an + b where a and b are constants

A function that takes the form of f(n) = an^2 +bn + c where a, b and c are constants

A function that takes the form of f(n) = alog2n (that’s a little low 2)

The power to which the base must be raised to make it equal to the number

A measure of the time complexity of an algorithm. It is a useful approximation of the time taken to execute an algorithm for a given number of items in a data set

Linearly e.g. 10,000 items will take approximately twice as long as 5,000 items to process

It halves the size of the problem at each pass

A permutation of n items is the number of ways the n items can be arranged

• Repetition allowed • No repetition allowed

Describing the time complexity of different algorithms

Each item is checked one after another until the desired item is found

Every item is checked

• Middle item is examined • If it is the desired item, the item is found • If not, depending on whether the current item is higher or lower than the desired item, half the list is eliminated • This is repeated until the item is found or proved to not be in the list

Hold items in a way that can be searched quickly and easily

The list must be sorted

O(log n)

O(n)

When there are only a small number of items

n-1 passes are made through the array, with each adjacent item being compared with the adjacent item and swapped if necessary