3-1-2: Comparing Algorithms

Constant Complexity O(1)- takes the same amount if time no matter how big the problem is.
e.g. Sorting the first ten records in a file- no matter how many files there are, it will take the same amount of time to sort the first ten files.

Linear Complexity O(n)- as the size of the problem increases, the time taken to solve the problem increases at the same rate.
e.g. mowing the lawn- if there is a 2m strip of lawn to be mowed, it will take half the time as a 4m stip of lawn.

Logarithmic Complexity O(log n)- as the size of the problem grows, the time taken to solve it increases also, but at a slower rate.
e.g. a binary search- you start by looking at the middle item of a list. If this is not the item being searched for, then you look at the middle item of the half of the list where the item is being searched for wil be found (if its in the list). You keep doing this until the item is found, or you discover the item is not in the list. The size of the list being searched through havles with each comparison.

Polynomial Complexity O(nk)- as the size of the problem grows, the time taken to solve it grows faster, but can be solved in a reasonable amount of time.
e.g. shaking hands with everyone in the room- if there are two people in the room, only 1 handshake will be needed. With 3 people in the room, 3 handshakes are needed. With 4 people in the room, 6 handshakes are needed, and so on.

Exponential Complexity O(kn)- as the size of the problem grows, the time taken to solve it grows by larger and larger amounts. Only small size versions of these problems can be solved in a reasonable amount of time.
e.g. Emperor's Chess Board Problem.

Factorial Complexity O(n!) even worse than exponential. Cannot be solved in a reasonable time.
e.g. The Travelling Salesman problem.