CODEWITHSUNDEEP
arrayscachingvectorcache-oblivious
newbiepp
newbiepp

Reputation: 95

Cache Oblivious Search

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 :)

Upvotes: 1

Views: 100

Answers (1)

dhruvbird
dhruvbird

Reputation: 6189

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.

Upvotes: 1

Related Questions