Jawaharlal Nehru Technological University Hyderabad B.Tech II DATA STRUCTURES Previous Question Paper (March - 2022 - R13)

Asymptotic notations are mathematical tools used to describe the limiting behavior of a function, specifically the growth rate of an algorithm's running time or space requirements as the input size n approaches infinity. They provide a high-level abstraction that ignores machine-dependent constants and lower-order terms to focus on the efficiency class of an algorithm.

The three primary notations are:

1. Big O Notation (O): Provides an asymptotic upper bound on the growth rate of a function. It represents the worst-case time complexity, ensuring the algorithm will not perform worse than this limit.
2. Omega Notation (Ω): Provides an asymptotic lower bound on the growth rate of a function. It represents the best-case time complexity, ensuring the algorithm will perform at least this well.
3. Theta Notation (Θ): Provides an asymptotic tight bound on the growth rate of a function. It occurs when the function is bounded both above and below by the same growth rate, indicating the average or exact complexity.

Applications of linked lists include:

1. Dynamic Memory Allocation: Linked lists are used to manage free memory blocks in operating systems.
2. Implementation of Stacks and Queues: They provide a flexible structure for implementing these data structures where the number of elements is not known in advance.

Advantages of doubly linked lists over singly linked lists:

1. Bidirectional Traversal: A doubly linked list allows traversal in both forward and backward directions, whereas a singly linked list only supports forward traversal.
2. Efficient Deletion: Deleting a node in a doubly linked list is more efficient if the pointer to the node is already known, as it does not require traversing from the head to find the preceding node to update its pointer.