Big O/Searching/sorting/algorithms Flashcards
What does O(1) represent
Constant time complexity (independent of num of elements)
O(n)
Linear time complexity (directly proportional to num of elements)
O(n^2)
Polynomial time complexity (example, directly proportional to the square of elements inputted)
O(2^n)
Exponential time complexity (doubles with each element added)
O(log n)
Logarithmic time complexity (increase at a smaller rate as the num of elements inputted)
Stacks: size()
Stacks: isEmpty()
Stacks: peek()
Stacks: push(element)
Stacks: pop
Queues: size()
Queues: isEmpty()
Queues: peek()
Queues: enqueue(element)
Queues: dequeue()
What are pre post and in examples of
Depth first
What is pre
Left
What is in
Bottom
What is post
Right
Only order you need to know
Post
Pseudocode for bubble sort
Pseudocode for insertion sort
How many functions is the merge sort algorithm made from
2
What are the two functions called in merge sort
MergeSort and Merge
What does MergeSort do
Divides its inputs into two parts and recursively calls MergeSort on each of those two parts until they are of length 1 and Merge is called
What does Merge do
Puts groups of elements back together in a special way ensuring the final result is sorted
Pseudocode for binary search
Pseudocode for linear search
Merge sort time complexity
O(nlogn)
