3-1-2 Comparing Algorithms

Problems with different time complexities

• Constant Complexity O(1) - takes the same amount of time no matter how big the problem is. (Sort the first ten records in file)
• Linear Complexity O(n) - as the size of the problem increases, the time taken to solve the problem grows at the same rate. (Cutting the grass)
• Logarithmic Complexity O(log n) - 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, but a slower rate. (Binary Search)
• Polynomial Complexity O(n^k) - 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. (Shaking hands with everyone in a room)
• Exponential Complexity O(k^n) - 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. (Emperor's chess board problem)
• Factorial Complexity O(n!) - even worse than exponential, cannot be solved in a reasonable time. (The travelling salesman problem)

Graph of the different time complexities

Key Terms:

Algorithm: a sequence of unambiguous instructions for solving a problem.

Computational complexity of an algorithm: measures how economical the algorithm is with time and space.

Time complexity of an algorithm: indicates how fast an algorithm runs.

Space complexity of an algorithm: indicates how much memory an algorithm needs.

Complexity of a problem: taken to be the worst-case complexity of the most efficient algorithm which solves the problem.

Basic operation: the operation contributing the most to the total running time.

Order of growth: assesses by what factor execution time increases when the size of the input is increased.

Asymptotic behaviour of f: the behaviour of the function f(n) for the very large values of n.

O(g): called big O of g, represents the class of functions that grow no faster than g.

Order of complexity: of a problem is its big O complexity.