| Give an explanation to how bubble sort works | Examine successive pairs in the list and swap them if necessary. Repeat this until the list is sorted |
| What are the advatages of bubble sort | Easy to underdstand
Easy to write
Requires very little memory space |
| Why is the bubble sort algorithm a time complexity of n^2 | Becasue it conatins a nested loop
The outer loop is done n times
And the inner loop done approximatly n^2 times |
| Why for bubble sort is the number of iterations of the inner loop not exactly n^2 | Inner loop iterates (n-1)(n-1) times
So the inner loop iterates n^2 -2n +1 times |
| Why can bubble sorts number of iterations be approximated to n^2 times? | As n becomes massive,
the number of iterations (n + 1)^2 = (n^2 -2n + 1) tends to just n^2
For large n 2n + 1 is nothing compared to n^2 |
| What is the relationship between the number of items and the algorithms’ performance for bubble sort? | the number of operations is proportional to the square of the number of items to be sorted |
| Is merge sort or bubble sort faster? | Merge |
| Explain how merge sort works | Divide the unsorted list into n sublists, each containing 1 element
Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining
This list is sorted |
| What is merge sorts complexity? | n log base 2 of n |
| What apporach does merge sort take? | Divide and conquer |
| Whats the big O notation of merge sort? | O(n log n) |
| Whats the worse case and average case complexity for any merge sort algorithm? | O(n log n) |
| Why for merge sort in Big O notation is the base of the log ignored? | It is becomes irrelevant as the number of items grows |
| Define time complexity? | The time complexity of an algorithm is the rate of growth of the number of operations in relation to the quantity of input data
Measurement of the amount of time required by an
algorithm for a given input of size (n) to solve |
| Order these from longest time to complete to least:
O(log n),
O(1),
O(n log n),
O(2^n),
O(n),
O(n^2),
O(n!) | O(n!)
O(2^n)
O(n^2)
O(n log n)
O(n)
O(log n)
O(1) |
| What is big O used for? | describe the worst-case complexity of an algorithm |
| Define big O notation | a measure of complexity which describes the performance of an algorithm on indefinitely large datasets
Descibes the complexity of a function |
| How do we compare the performance of sorting algorithms? | Number of basic operations they perform |
| Big O notation:
What do O(23n^2) and O(3n^2) and O(3000n^2) all equate to? | O(n^2) |
| Give a way to optimise a bubble sort algotihm | The inner loop takes into account that after each pass the last non sorted index place is sorted so there's no need to loop to that point again
Also a recognistion (through a variable called swapped maybe) of when the algrothm has sorted the problem so no unnecessary additional passing through is done |
