time complexity Flashcards
1
Q
time complexity def
A
desc how t taken to execute algo grows w size of input data (X indicative of actual t)
2
Q
what does small t complexity suggest
A
more efficient/consistent performance (NOT faster)
BUT
for large num of items, t complexity correlates to speed (P: for large num of items, __ is faster)
3
Q
time complexity of sort algo
A
bubble sort: O(n²) & best case is O(n) for mostly sorted arrays
insertion sort: O(n²)
merge sort: O(n log n)
quick sort: O(n log n) bt worse case is O(n²) for mostly sorted arrays.
4
Q
time complexity of search algo
A
linear search: O(n)
binary search: O(logn) [if BST maximally unbalanced then O(n)]
hash table search: O(1) [w hash collisions then O(n)]