Complexity - dennis1303/Panda GitHub Wiki

Here lets talk about the individual complexities of the operations being done first.Lets assume arrayList is an ArrayList() object and hashMap is a HashMap<Integer,Integer>() object.

• Time complexity of a hashMap.get(int k) and hashMap.put(int k,int v) is O(1).
• Time complexity of arrayList.get(int index) is O(1).
• Time complexity of arrayList.remove(int index) is O(n).
• Time complexity of arayList.indexOf(int value) is O(n).

Now lets calculate time complexities of put and get methods of LRUCache:

• Since get method of LRUCache just adds an entry to an ArrayList and an entry to HashMap in case of capacity of cache not been reached and the page already present in cache, therefore the complexity of get method is O(1) + O(1) ,i.e. O(1).

• In case of cache memory not full and the required page not present in cache, 3 operations are made, i.e. insertion to ArrayList, insertion to HashMap and remove from ArrayList.The removal from ArrayList also calls internally indexOf method which is an O(n) implementation.So in worst case, it can go to O(n^2) complexity.

• In case of cache memory full and required page not found in cache, three operations are done, i.e. insertion to ArrayList, insertion to HashMap and eviction of least recently used page (which is O(n) operation as it calls arrayList.remove(0)).So it is overall an O(n) implementation.

• In case of cache memory full and required page present in cache, we do three operations, i.e. insertion to ArrayList, deletion from ArrayList and insertion to HashMap. So it is also overall O(n) operation.