Amortised Cost Analysis (15 points) In a web caching software, there are n URLs stored in a doubly linked list with head and tail pointers, pointing to the start and the end of the list respectively. Whenever a new URL is cached, it is stored (or inserted) at the end of the list in constant time using the tail pointer. Whenever any URL (say www.usc.edu) is searched in the cache, the search starts from the head of the list and then the list is traversed until the target URL is found. If the target URL is found at a location i, where in, the search is stopped ( Call it the search operation) and the target URL is moved towards the head of the list by 1 index (Call it the move operation). The cost for each search operation would be i (i.e., original index of the target URL) and the cost for each move operation is c (where c is a positive constant). Given that www.usc.edu is present in our cache, calculate the amortized time complexity for searching www.usc.edu considering the worstcase scenario. You can assume that the number of times the URL www.usc.edu is searched would be less than or equal to the total number of URLs already cached in the list, and you can also assume that you dont search for any websites other than www.usc.edu.