Big O notation Flashcards
Big O notation describes what in an algoritm
the performance or complexity of the algorithm. measures how time and space requirements increase as the number of elements increase (not a test of speed)
Constant run time complexity
0(1), regardless if array contains 10 or 10000 items, run time is the same
linear run time complexity
O(n) - performance will grow linearly and in direct proportion to the size of the input data set.
Algorithm where complexity is directly proportional to the square of the size of the input data set
O(n^2)
AKA quadratic run time complexity
- common for sorting algorithms
logarithmic run time complexity
O(log n) - data used is decreased by approx 50% each pass through the algorithm
O(n^c)
polynomial time
O(n log n)
linearithmic time
linearithmic time
O(n log n)
polynomial time
O(n^c)
exponential time
O(2^n)
O(2^n)
exponential tim
factorial time
O(n!)
run time of sorting and searching algorithms
sorting - n^2 unless it is quick sort where it is O(n log(n)) (with a worst case of O(n^2)
searching - n unless it is binary search where it is log(n)
