JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD MCA 2021 DATA STRUCTURES AND ALGORITHMS Previous Question Paper (July/August - 2021 - R17)

To sort the array [10, 6, 3, 7, 17, 26, 56, 32, 72] using Quick Sort, we select the last element as the pivot.

1. Initial array: [10, 6, 3, 7, 17, 26, 56, 32, 72]. Pivot = 72. All elements are smaller than 72, so 72 remains at the end.
2. Sub-array [10, 6, 3, 7, 17, 26, 56, 32]. Pivot = 32. Elements smaller than 32 are [10, 6, 3, 7, 17, 26], elements larger are [56]. Array becomes [10, 6, 3, 7, 17, 26, 32, 56, 72].
3. Sub-array [10, 6, 3, 7, 17, 26]. Pivot = 26. Elements smaller are [10, 6, 3, 7, 17]. Array becomes [10, 6, 3, 7, 17, 26, 32, 56, 72].
4. Sub-array [10, 6, 3, 7, 17]. Pivot = 17. Elements smaller are [10, 6, 3, 7]. Array becomes [10, 6, 3, 7, 17, 26, 32, 56, 72].
5. Sub-array [10, 6, 3, 7]. Pivot = 7. Elements smaller are [6, 3]. Array becomes [6, 3, 7, 10, 17, 26, 32, 56, 72].
6. Sub-array [6, 3]. Pivot = 3. Swap results in [3, 6].
7. Final sorted array: [3, 6, 7, 10, 17, 26, 32, 56, 72].

Asymptotic notations are mathematical tools used to describe the limiting behavior of a function as its input grows towards infinity. The primary properties are:

• Big-O Notation (O): Provides an asymptotic upper bound on the growth rate of a function. If f(n) = O(g(n)), then f(n) <= c*g(n) for all n >= n0.
• Omega Notation (Ω): Provides an asymptotic lower bound. If f(n) = Ω(g(n)), then f(n) >= c*g(n) for all n >= n0.
• Theta Notation (Θ): Provides an asymptotic tight bound, meaning the function is bounded both above and below by the same growth rate. f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)).
• Transitivity: If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n)). This applies to all three notations.
• Reflexivity: Any function is asymptotically bounded by itself, e.g., f(n) = O(f(n)).
• Symmetry: f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n)).