a) The first time you run algorithm A on a dataset of n elements; it is faster than
algorithm B. The second time you run algorithm A on a dataset of n elements; it is slower than
algorithm B. Explain how this is possible. Give an example for algorithm A and algorithm B.
b) If both have n nodes and are sorted smallest to largest, will it be faster to find
the largest value in a sorted linked list or a minimum-level BST? Explain.
For (a) this hint may help:
There are several ways to characterize algorithm complexity. In particular, three parameters are important: best-case, worst-case and average-case complexity. The actual complexity of the algorithm may depend on the input. For example, any sorting algorithm quicksort has average-case complexity of O(n log n), but has a worst-case time complexity for O(n^2). By contrast, insertion sort has best-case complexity of O(n) and worst-case complexity of O(n^2).
If both of these algorithms are applied to two datasets, D1 and D2, perhaps:
D1 completes in O(n log n) under quicksort and O(n^2) under insertion sort
D2 completes in O(n log n) under quicksort, but O(n) [best case!] under insertion sort
Wouldn't this satisfy the criterion?
Can you think up another example?
For (b) I'll ask you a question:
If you had a sorted linked list, how would you find the largest value?
If you had a minimal BST, how would you find the largest value?
For each answer, how many operations does that require (in terms of the size of the list)?
All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.
If database is ordered from low to high and you have A as bubble sort (that sorts low to high), it will take time of O(n) to "sort" n elements on the database. B could be a heapsort that always take O(nlogn) and sort database high to low.
Once you run A gain it will take O(ną2) and B will take O(nlogn).
For the second question, to find the largest value on a linked list you have to go element by element following the pointer so that is O(n), but to find the largest element in a BST you walk from the root to the far most right-down element which will take you O(log2(n)) as the tree has only O(log2(n)) levels.