Title O(N log N) Sorting Algorithms & Hash Tables with Collision Resolution[1].pptx

jjj

1. TITLE: O(N LOG N) SORTING ALGORITHMS & HASH TABLES WITH COLLISION RESOLUTION Roll no: 22BSCS016 Muzammil Ahmed 22BSCS019 Asim Raza

2. Heap Sort Overview Definition: A comparison-based sorting algorithm using a binary heap. Properties: Implemented using an array representation of a heap. Uses the heap property (parent nodes are larger/smaller than children). Time Complexity: O(N log N) for all cases (best, average, and worst). Space Complexity: O(1) (in-place sorting, no additional memory required). .

3. Steps of Heap Sort Build a Max Heap from the input array. Extract the Maximum Element (root) and swap with the last element. Heapify the remaining elements to restore heap structure. Repeat extraction and heapify until only one element remains.

4. Hash Tables A Hash Table (or Hash Map ) is a data structure that maps keys to values using a hash function . It provides fast data retrieval , making operations like insertion, deletion, and lookup efficient, typically in O(1) time complexity on average. How a Hash Table Works Key-Value Storage : Each entry consists of a key and its corresponding value . Hash Function : A function converts the key into an index (hash code) that determines where the value is stored. Array-Based Storage : The hash table is typically implemented as an array , where each slot stores values based on their hash code.

5. Collision Handling : When two keys produce the same index, a strategy is required to store both values (e.g., chaining, open addressing). Operation Description Time Complexity (Average) Time Complexity (Worst) Insert (put) Store a key-value pair O(1) O(n) (if too many collisions) Search (get) Retrieve a value using the key O(1) O(n) (in case of collisions) Delete (remove) Remove a key-value pair O(1) O(n) Operations in Hash Table

6. Hash Function A hash function converts a key into an integer index within a fixed-size array. Properties of a Good Hash Function Deterministic → Same key should always return the same index. Uniform Distribution → Spread keys evenly to minimize collisions. Efficient Computation → Quick to compute for fast lookups. Collision Handling Techniques Since different keys may generate the same hash index (collision), we use collision resolution techniques. Chaining (Linked List) Each index stores a linked list of key-value pairs. If multiple keys hash to the same index, they are stored in a list at that index. ✅ Pros : Handles collisions well, dynamic storage. ❌ Cons : Can become inefficient if lists grow too long.

7. Open Addressing (Linear Probing) If a collision occurs, search for the next empty slot . Linear Probing : Check the next slot ( index + 1 ). Quadratic Probing : Check slots using (index + i²) % size . ✅ Pros : No extra memory for linked lists. ❌ Cons : Causes clustering (too many occupied slots in sequence). Advantages Fast lookup, insert, and delete (O(1) on average). Efficient memory usage with dynamic resizing. Used in caching, indexing, and key-value storage . Disadvantages Collisions slow down performance (O(n) in the worst case). Uses extra memory compared to arrays/lists. Not ordered (unlike binary search trees or linked lists).

8. THANK YOU