Problem 3. Consider the following recurrence, defined for n a power of 4 (for the time of some algorithm): T(n) = 3 if n = 1 2T(
n/4) + 4n + 1 otherwise (a) Calculate T(16) by hand. Show your work. (b) Use the tree method to solve the recurrence exactly, assuming n is a power of 4. (c) Use the formula to calculate T(1). Show your work. (d) Use the formula to calculate T(4). Show your work. (e) Use the formula to calculate T(16). Show your work. (f) Use Mathematical Induction to prove that your formula is correct in general.
1 answer:
You might be interested in
Answer:
See the attached pictures for detailed answer.
Explanation:
The cache contain 8K number of blocks.each block has 16 Byte worth of data. Each of these bytes are addressable by block offset. Now, each of these blocks are addressable and their address is provided by line offset or set offset. If block number is given in Decimal format then the block to which that block will be mapped is given by expression
mappedToBlock = (bNumber)mod213
TAG and valid but consititues something called cache controller. TAG holds the physical address information because the TAG in physical address get divided into TAG and line offset in cache address. Valid bit tells status of blocks. If it is 1 then data blocks are referred by CPI else not.
