in bellman ford algo v-1 times will give you the shortest path but if there is any -ve edge cycle to check you have to perform 1 more cycle . Why V-1times ? simple , a vertices is connected to atmost V-1 vertices to check them you need V-1 times ( there is no -ve edge cycle ) .
8 million = 8*2^10*2^10 =2^23 So address is 23 bits. Word offset its = 6 (2*6=64) No of bits to identify a Block= 8(2^8 = 256) No of bits to indentify tag= 23-6-8=9 1) Additional memory for tag=(256*9)/8= 288 bytes 2) Total size of the cache =Cache size +Tag memory + Dirty bit memory +Valid bit memory =256*64 +(256*9)/8 + 256/8 + 256/8
Consider a 8 million word main memory and 256 block cache.Both partitioned into 64 words block.What is the size of additional memory for tags? Size of the cache? consider direct mapping is used and word size 1 byte.
lg *n, (Inverse Ackermann function) is the number of times we can take log repeatedly until we get 1. This function can almost be considered constant for all practical purposes. There shouldn't be any confusion regarding options C and D as n! is asymptotically larger than lg n. A) lg (lg * n) B) lg * ... can write B as lg * (lg n) = lg * n - 1. So, A is asymptotically lower than B. A < B < D < C.
In topological sort, in the inner loop we consider only "adjacent vertex". So, the complexity at max can be O(|V|2) which happens when |E| = |V|2. In Bellman Ford algorithm, the inner loop is run for each and every edge.