(3) Algorithms II Flashcards
Which issue do we need to consider with regard to efficiency?
- Time it takes an algorithm to solve a problem
2. Allocation of space (memory) needed for computation
Definition Time Complexity
Number of steps the algorithm needs to solve a given problem, as a function of the size of the input (relevant operation is considered and not the hardware or time (e.g. minutes))
What is the Big O-Notation good for?
- Asymptotic upper bound of the algorithm
- Worst case time complexity
- Used to compare algorithms
What is the time complexity of naive search?
O(n), n = number of elements in the array
What are the steps of the binary search algorithm?
- Start in the middle of the array
- If element ? searched element-> done
- If element < middle element, go to left part
- element > middle element go to right part
What is the time complexity of binary search (incl. derivation)?
O(log n)
-> we divide the array n/2 times
What is a prerequisite to apply binary search?
Array must be sorted
Does it always make sense to sort prior to searching?
Depends on how much sorting costs and how much more you search compared to sort
What is the principle of bubble sort?
- steps through list and compares elements next to each other
- if the elements are unsorted they are swapped
- repeat until no more swaps are necessary
What is the time complexity of bubble sort (worst and best case)?
Worst case: O(n^2)
Best case: O(n) -> Bubble sort looks at all elements at least once
What is the principle of merge sort?
- divide the unsorted array into two arrays
sort each of the two arrays recursively until array size= 1 - Merge the two sorted arrays into one sorted array
What is the time complexity of merge sort?
O(n * log(n))
- n steps to split
- n steps to merge
- 2T(n/2) analogous computation for each of the two bisected arrays
