Suggest an editImprove this articleRefine the answer for “Why does the choice of data structure affect an algorithm's O(n) complexity?”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)The choice of **data structure** affects an algorithm's asymptotic complexity because different structures give different execution speeds for basic operations: search, insertion, deletion, access by index, and so on. **Key point:** an algorithm's O-notation is the sum or combination of the O-notations of the data structure's operations, which is why the data structure is the foundation of efficiency.Shown above the full answer for quick recall.Answer (EN)ImageThe choice of data structure affects an algorithm's asymptotic complexity because **different structures give different execution speeds for basic operations**: search, insertion, deletion, access by index, and so on. An algorithm almost always consists of a combination of these operations, so their speed directly determines the overall complexity. Key points: --- ### **1. Different structures - different operation execution time** For example, searching for an element: | Structure | Search | |---|---| | Array (unsorted) | O(n) - you have to scan everything | | Binary search tree (balanced) | O(log n) | | Hash table | O(1) on average | An algorithm that performs a search 1000 times will take 1000×O(n) on an array and 1000×O(1) on a hash table. These are **different orders of speed**, even though the algorithm's own logic may be identical. --- ### **2. The data structure determines the way of access** - To get an element by index in an array: **O(1)** - To get an element in a linked list by index: **O(n)** (you need to walk the chain) The same algorithm "get element #k" changes complexity only because of the structure. --- ### **3. Structures are optimized for different tasks** There is no universal structure, so: - if you need frequent insertions in the middle, a list gives O(1), an array gives O(n) - if fast search matters, a tree or a hash table is better than a list An algorithm running on an *unsuitable structure* automatically becomes slower at the asymptotic level. --- ### **4. The bottom-line rule** **The algorithm's O-notation = the sum or combination of the O-notations of the data structure's operations.** That is why the data structure is the foundation of efficiency. --- If you want, I can go further and break this down with a concrete example (for instance, why BFS uses a queue and Dijkstra uses a heap) to see how the structure directly "shapes" the complexity. Continue with examples?For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.