Consider the following two functions, f(n). For each of these two functions, wri
ID: 3882855 • Letter: C
Question
Consider the following two functions, f(n). For each of these two functions, write a function g(n) such that f(n) = O(g(n)) and f(n) notequalto theta (g(n)). (i) f(n) = nlogn (ii) f(n) = 3n^2 + 2n + 1 Consider a scenario wherein 100,000 objects (each of size: 40 bytes) need to be stored in a List. (a) Determine the memory (in bytes) that would need to be allocated to the List if it were to be implemented as a: (i) Dynamic array: (ii) Singly Linked List and (iii) Doubly Linked List. (b) If we were to do frequent insert and delete operations for the above List, which implementation (dynamic arrays or Linked List) would you prefer and why?Explanation / Answer
Q 2)
(a)
(i) No of objects = 100000
Size of each object = 40 bytes
Therefore, Total Size = No of objects * Size of each object
= 100000 * 40
= 4000000
(ii) Each node of a singly linked list contains one object and a pointer.
Let size of each pointer to the node be s.
No of Nodes = 100000
Size of each Nodes = 40 + s
Therefore, Total Size = No of objects * Size of each object
= 100000 * (40 + s)
(iii) Each node of a doubly linked list contains one object and a pointer.
Let size of each pointer to the node be s.
No of Nodes = 100000
Size of each Nodes = 40 + s + s = 40 + 2s
Therefore, Total Size = No of objects * Size of each object
= 100000 * (40 + 2s)
(b)
In case of frequently insert and delete operations, we would use a linked list as it would be more efficient and would take less time and less number of operations. In a dynamic array, if we delete an element, we would have to shift all the elements after the element to be deleted one place backward, which would take a lot of time and a lot of operations.But in linked list this is not the case. We just have to adjust some pointers and its done. Hence, in linked list less number of operations are required.