Basic Algorithm Theory Flashcards
1
Q
What does it mean if an algorithm is incremental?
A
An algorithm is incremental if it does not need to re-compute everything after a small change
e.g. if you add an element to a sorted list, can the algorithm sort this new element without a large number of iterations
1
Q
What does it mean if an algorithm is stable?
A
An algorithm is stable if it maintains the relative order among elements when sorting
2
Q
What is the reference complexity of two array based sets, with size n and m for union, intersection and difference
A
O(n * m * C), where n & m are size of array, and C is cost of comp
