Answer:

An algorithm is said to be incremental if it does not need to recompute everything after a small change. For example: adding an element to a sorted list and sorting it again. If it only takes a few iterations, it would be called incremental. 

Bubble sort is incremental when the element is added to the front of the list because it will reach its correct position in the list in the first iteration. But if you add it to the end of the list, the number of iterations required would depend on the position of the element. (Include an example)

Adding onto this ^^: 

This is because of the invariant that mentions that in each traversal, the largest unsorted element will get to its final position.    

Eg: 

Original sorted list: [3, 6, 10, 14, 18, 20] 

After appending 13 at the end: [3, 6, 10, 14, 18, 20, 13]

Note that 14, 18 and 20 are not in their final positions and require 3 traversals of the list in order to sort the list. 

However, if we append to the front: [13, 3, 6, 10, 14, 18, 20], only one traversal of the list is required (refer back to the invariant)

Alternate answer:

An algorithm is incremental if it does not need to re-compute everything after a small change:

– Can reuse most of the work already done to handle the change 

 A sorting algorithm is incremental if it can:

 – Given a sorted list and one new element 

– Use one (or a few) iterations of the algorithm to return a sorted list that has the new element

Bubble sort 1 is not incremental because it would require (n – 1) iterations if the new element added is smallest. However, the optimised bubble sort 2 is incremental when the new element is added to the front.