Unit I – Data Structures & Complexity Analysis (Full Notes with Q&A;)
Q1) What is a data structure?
A data structure is a way to organize, store, and operate on data so that tasks like insertion,
deletion, search, and traversal can be performed efficiently.
Q2) Linear vs Non-linear data structures
Linear structures arrange elements sequentially (arrays, stacks, queues, linked lists), while
non-linear structures organize data hierarchically or in networks (trees, graphs).
Q3) Abstract Data Type (ADT)
An ADT specifies the operations and their behavior without detailing the implementation (e.g., Stack
ADT has push, pop, top).
Q4) Time & Space Complexity
Time complexity measures how runtime grows with input size, while space complexity measures
the extra memory required.
Q5) Big-O, Omega, Theta
Big-O: Upper bound, Omega: Lower bound, Theta: Tight bound. Example: T(n) = 3n² + 10n + 5 is
Θ(n²).
Q6) Searching Algorithms
Linear Search scans sequentially (O(n)); Binary Search halves the search space on sorted data
(O(log n)).
Q7) Sorting Algorithms
Bubble Sort: O(n²) worst, adaptive with flag; Selection Sort: O(n²), not stable; Insertion Sort: O(n)
best, O(n²) worst, stable and adaptive.
Sorting Algorithms Comparison
Algorithm Best Time Average Time Worst Time Space Stable Notes
Bubble (flag) O(n) O(n²) O(n²) O(1) Yes Adaptive with flag
Selection O(n²) O(n²) O(n²) O(1) No Few swaps
Insertion O(n) O(n²) O(n²) O(1) Yes Great for nearly sorted
Linear Search O(1) O(n) O(n) O(1) - Unsorted/one-off lookups
Binary Search O(1) O(log n) O(log n) O(1) - Requires sorted data
