Time complexity

Page 1

Orders.

Constant O(1) - When run time is not affected by the size of the input. e.g. the first element of an array. "A bigger class does not affect the ability to shout at Rose"

Linear O(n) - Run time increases linearly with the size of the input. e.g. if input doubles, run time doubles. The worst case scenario is that the desired item is at the end of the array. y = x

Polynomial O(n²) - Run time of an algorithm increases by the power of n of the input squared. e.g. checking an array for duplicates. Happens in algorithms with nested loops y = x² or x³ etc... etc...

Exponential O(2ⁿ) - Doubles in run time for each increase in the size of the input. y = 2ˣ

Factorial O(n!) - Increases by the factorial of the size of the input. input size of 3 = 1x2x3 of 8 = 1x2x3x4x5x6x7x8. very big, very quick.

Logarithmic O(log (n)) - Increases linearly as the input doubles. More efficient than linear as it gets more efficient as the size of the input gets bigger. e.g. Binary Search

Intractable - Not able to be solved within a reasonable amount of time.

Two intractables of these order = Polynomial and Factorial

Page 2

Exam Question - Explain what is meant by an intractable problem:

An intractable problem is one that can't be solved in a reasonable amount of time, but is technically solvable

Exam Question

Page 3

Page 4