Big O Notation - Time Complexity

Big O notation is used to describe the efficiency of an algorithm, focusing on its time complexity (how the execution time grows with input size) and space complexity (how much extra memory is needed). It expresses the worst-case scenario performance of an algorithm.

Common Complexities

• O(1) – Constant time: The algorithm's runtime does not change with the input size.
  • Example: Accessing an element in an array by index.
• O(log n) – Logarithmic time: The algorithm reduces the problem size by a constant factor with each step.
  • Example: Binary search in a sorted array.
• O(n) – Linear time: The runtime grows proportionally with the input size.
  • Example: Traversing a list of n elements.
• O(n log n) – Linearithmic time: The algorithm performs a linear number of operations for each logarithmic division.
  • Example: Merge sort and quicksort in their average cases.
• O(n²) – Quadratic time: The runtime grows quadratically with input size.
  • Example: A double nested loop, like in bubble sort or selection sort.
• O(2^n) – Exponential time: The runtime doubles with each addition to the input size.
  • Example: Solving the traveling salesman problem using brute force.
• O(n!) – Factorial time: The runtime increases factorially with the input size.
  • Example: Generating all permutations of a set.

Data Structures and Their Time Complexities

1. Hash Table
   • Access: O(1) (average case), O(n) (worst case due to collisions)
   • Search: O(1) (average case)
   • Insertion/Deletion: O(1) (average case)
2. B-Tree
   • Access/Search: O(log n)
   • Insertion/Deletion: O(log n)
   • Space Complexity: O(n)
3. Balanced Binary Search Tree (e.g., AVL Tree, Red-Black Tree)
   • Access/Search: O(log n)
   • Insertion/Deletion: O(log n)
4. Binary Search Tree (BST)
   • Access/Search: O(log n) (average), O(n) (worst case, unbalanced)
   • Insertion/Deletion: O(log n) (average), O(n) (worst case)

---

B-Tree Balancing

B-Trees are inherently balanced during indexing, so they do not require rebalancing in the way that some other tree structures, like AVL trees or Red-Black trees, do.

• Balanced Nature: B-Trees are self-balancing by design. When you insert or delete keys, the tree is adjusted to maintain its balance. This is achieved by splitting or merging nodes as necessary during insertions and deletions, ensuring that all leaf nodes remain at the same level and the tree remains balanced.
• Indexing: During the indexing process, as new keys are inserted into the B-Tree, the structure automatically ensures that the tree remains balanced. This is done by maintaining certain properties, such as:
  1. All nodes (except the root) having at least a minimum number of children.
  2. The height of the tree being kept as low as possible to optimize search operations.

Because of this, B-Trees are particularly well-suited for use in databases and file systems where efficient data retrieval and storage are critical.

---

5. Array (Fixed size)
   • Access: O(1)
   • Search: O(n)
   • Insertion: O(n) (if resizing required)
   • Deletion: O(n)
6. Linked List
   • Access: O(n)
   • Search: O(n)
   • Insertion/Deletion (at head): O(1)
7. Heap (Priority Queue)
   • Access (max or min): O(1)
   • Insertion/Deletion: O(log n)
8. Graph (Adjacency Matrix/Adjacency List)
   • Search (DFS, BFS): O(V + E), where V is the number of vertices and E is the number of edges
9. Stack/Queue
   • Access: O(n)
   • Insertion/Deletion: O(1)

© Kevin Luzbetak