1

Please forgive this stupid question, but I didn't find any hint by googling it.

If I have an array (contiguous memory), and I search sequentially for a given pattern (for example build the list of all even numbers), am I using a cache-oblivious algorithm? Yes it's quite stupid as an algorithm, but I'm trying to understand here :)

newbiepp
  • 95
  • 6

1 Answers1

1

Yes, you are using a cache-oblivious algorithm since your running time is O(N/B) - i.e. # of disk transfers, which is dependent on the block size, but your algorithm doesn't depend on a particular value of the block size. Additionally, this means that you are both cache-oblivious as well as cache-efficient.

dhruvbird
  • 6,061
  • 6
  • 34
  • 39