In this section the execution time w.r.t. instruction fetch overhead is analyzed. Other factors, e.g. data references to main memory, may add to the execution time but should not be adversely effected by the benefits of instruction caching.
For any uncached system, let the fetch time of one instruction be n
cycles. Furthermore, let i be the number of instructions executed.
Then, a lower bound for the time for this execution is
For a cached system, let i=h+m be the number of instructions
executed where h and m are the number of hits and misses respectively.
Assume a cache look-up penalty of one cycle [, ]. Since a
cache look-up always has to be performed before it can be decided
whether the program line associated with an instruction has to be fetched
from main memory, the lower bound for an execution in a cached system is
For the bit-encoded cached system, let i=h'+m' be the number of
instructions executed where h' and m' are the number of
instructions fetched from cache and memory
respectively
. Then, a lower time bound can be given as
There is both spatial and temporal locality inherent in the code of almost all programs. For instance, assume that a cache line consists of multiple instructions. The first reference to an instruction in such a line may cause a miss. But if instructions are executed sequentially, consecutive references to instructions of the same line will result in hits. Also, assume that some portion of the code that can be executed in a loop does not conflict with any other program lines that can be accessed by the loop. Subsequent references to this code in the same execution of the loop will also result in hits. Based on this observation, we can assume the following inequalities for an average execution:
, 
, and h' < h.
On average, we conclude with the following relation for an execution.
