time complexity

Question 1

time complexity def

Answer 1

desc how t taken to execute algo grows w size of input data (X indicative of actual t)

Question 2

what does small t complexity suggest

Answer 2

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)

Question 3

time complexity of sort algo

Answer 3

bubble sort: O(n²) & best case is O(n) for mostly sorted arrays
insertion sort: O(n²) & best case is O(n) for mostly sorted arrays
merge sort: O(n log n)
quick sort: O(n log n) bt worse case is O(n²) for mostly sorted arrays (bc pivot is far frm median)

Question 4

time complexity of search algo

Answer 4

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)]