Big O notation Flashcards
1
Q
Linear
A
O(n)
- performance declines as data set grows
- execution time is directly proportional to the input size
2
Q
Logarithmic
A
O(log n)
- halves data set in each pass
3
Q
Constant
A
O(1)
- always executes in same amount of time regardless of data set size
4
Q
Logarithmic example
A
- Binary search algorithm
- with each pass, it halves the input data set
5
Q
Polynomial
A
O(n2)
- performance is proportional to the square of the size of the data set
- significantly reduces efficiency with increasingly large data sets
6
Q
Polynomial example(s)
A
- bubble sort
- insertion sort
- multiple comparisons
e.g. for 3 inputs, 9 operations would be made
7
Q
merge sort
A
- splits data into individual lists then merges
8
Q
insertion sort
A
- makes first value sorted list
- then inserts each item into sorted list
9
Q
bubble sort
A
- looks through each item in turn
- compares them
- then swaps
10
Q
quick sort
A
- choose a pivot
- compare each element to the pivot
- put items < pivot into left sublist
- put items > pivot into right sublist
- choose pivot in each sublist
- then swap data items around
- repeat until each item has become a pivot/list is sorted
11
Q
space
A
- merge will require more memory as number of elements increase
- insertion will not require more space than original data set
12
Q
best time
A
- insertion increases at same rate as number of elements: linear O(n)
