Question

What is the time complexity to identify required block in cache if direct mapping scheme is used while CPU generates n bit main memory address? What is the time complexity of getting a required cache block in associative mapping?

Answer 1

In direct mapped cache, a particular address will belong to only one particular cache block. So to identify if a particular memory block is in cache or not, we need to check only one cache block and check it's tag bit.

So the time complexity is O(1).

In an associative mapping, a memory block can belong to any block of cache. Thus to check if a block is present in cache or not, we have to check entire cache blocks. All the block have to be checked with the tag bits of given memory address.

So time complexity is O(# of cache block)

If you have any questions comment down and please? upvote thanks...