Algorithms can either be oblivious or non-oblivious, but what is the actual difference between the two?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
Oblivious means that the control flow is independent of some properties of data. For example Bitonic Sort (also known as sorting net_ is oblivious, because it always compares the same elements disregarding data it gets, while Quick sort (or merge sort, or any adaptive sorting) are non-oblivious, because the algorithm steps change based on data. Bitonic sort does exactly the same steps in the best and the worst case, while non-oblivious algorithms may vary from $n$ steps to $n^2$ (for example).
This definition for cache is very similar, it means that it takes advantage of cache independently of its size (cache length).
