Big O notation
Give two rules for using big O notation
- Remove all terms apart from the one with the largest exponent
- Remove any constants
Define O(1)
An algorithm that executes data in the same amount of time regardless of the size of the data set
Define O(n)
Describes an algorithm whose run time grows linearly with the size of the input.
Define O(log n)
Describes an algorithm where time increases very slowly as dataset grows. Halves the dataset in each pass
Define O(n^2)
performance is proportional to the square of the size of the dataset
Define O(2^n)
An algorithm whose run time increases quadratically as the dataset grows. Doubles the dataset in each pass
Define 'Best case complexity'
The algorithm that performs most efficiently e.g. a linear or binary search finding the correct item in the first search
Define 'Average case complexity'
An algorithm that performs neither at its best or worst on any given data. e.g. a linear search looking for an item thats in the middle of a list
Define 'Worst case complexity'
An algorithm that is the least efficient e.g. a linear search finding the item in the last position
Why is Big O Notation measured by the worst case performance
It allows programmers to accurately select algorithms for a problem. (Algorithms with the most reliable performance)