I never thought insertion and deletion operations have more time complexity than sorting and searching.
But when learning DSA in C, this point came up, and I couldn't accept it until I gained a clear understanding of why that statement is correct.
Let’s first see it with a simple example: we have a list of phone numbers with their owner names. We need to sort by name, then search for an owner to call. Complexity: sort is O(n log n) with quicksort as a one-time operation for all records. After sorting, binary search is the standard option used across systems.
In C, these are already provided as functions: qsort and bsearch from <stdlib.h>.
When I looked at insert and delete operations in an array, I didn't find any built-in functions. That's why I'm not aware of them; they need custom implementation.
It's important to know how insert and delete behave on an array.
Two things I want to clear here:
1
- Insert doesn't override any element.
- Insert is not like arr[i] = value.
2
- Delete doesn't leave any empty place in the continuous element list.
- Delete is not like arr[i] = null.
It keeps the array consistent without breaking or missing values.
Based on that insert and delete don't change or override existing values; one important thing introduced is the concept of shifting.
For insert, it needs to move all values after index i one position to the right, making space for the new element. Same for delete: move all values after index i one position to the left.
Both operations take O(n) time each.
Now this information convinces me: insert and delete have more complexity than sorting and searching.
One key insight: when considering each individual element operation, sort O(n log n) has lower complexity than insert/delete O(n). Insert/delete O(n) > sort O(n log n). At first it looks wrong, but when viewed broadly: sorting is a one-time cost for all elements, while insertion/deletion is O(n) for just one element operation.
This is theoretical understanding, but we need proof of actual use in real systems.
All these C operations (sort, search, insert, delete) are used in real systems: operating systems, kernels, database systems, and CLI tools that perform read/write (insert/delete) or sort/search operations.
Operating system example: file systems use it for creating new files/folders, deleting them, sorting, and finding. Database systems: INSERT, DELETE, and SELECT operations use these algorithm concepts. Linux kernel: Functions for sort and search exist in the Linux source code, implementing these concepts.
When our phone adds a new contact or searches for it, that also calls these algorithms.
Most systems use quicksort and binary search for optimal performance.