Data Structures Time Complexity

Data Structures and Their Operations

• Array (Static)

  • Search: O(N)

  • Insert: O(1)

  • Delete: O(1)

• Sorted Array

  • Search: O(log N)

  • Insert: O(N)

  • Delete: O(N)

• Sorted Linked List

  • Search: O(N)

  • Insert: O(N)

  • Delete: O(1)

• Balanced Binary Search Tree (BST)

  • Search: O(log N)

  • Insert: O(log N)

  • Delete: O(log N)

• Stack (using Linked List or ArrayList)

  • Push: O(1)

  • Amortized for ArrayList

  • Pop: O(1)

  • Amortized for ArrayList

• Queue (Linked List)

  • Enqueue: O(1)

  • Dequeue: O(1)

• Queue (ArrayList Non-Circular)

  • Enqueue: O(N) worst case / O(1) amortized

  • Dequeue: O(N)

• Queue (ArrayList Circular)

  • Enqueue: O(1) amortized

  • Dequeue: O(1) amortized

• Priority Queue (using Heap)

  • Enqueue: O(log N) amortized

  • Dequeue (remove max): O(log N) amortized

  • Build Heap from Array (Build-Heap): O(N)

• AVL Tree

  • Insert: O(log N)

  • Delete: O(log N)

  • Search: O(log N)

• Red-Black Tree

  • Insert: O(log N)

  • Delete: O(log N)

  • Search: O(log N)

• Hash Table

  • With good hash function, Search: O(1) average

  • Hash Table (Chaining): Insert: O(1) average

  • Hash Table (Probing): Insert: O(1) average

  • Worst Case Search: O(N)

Sorting Algorithms

• Selection Sort

  • Time Complexity (Best/Worst/Average): O(N^2)

• Bubble Sort

  • Best Case: O(N)

  • Worst/Average: O(N^2)

• Quicksort

  • Best/Average: O(N log N)

  • Worst: O(N^2)

• Heapsort

  • All Cases: O(N log N)

Space Complexity

• Selection Sort, Bubble Sort, Heapsort: O(1)

• Quicksort: O(log N) (recursive stack) or O(N) (worst case without optimizations)

Algorithms

• Dijkstra's Algorithm

  • Time Complexity: O((n + m) log n)

• BFS Shortest Path

  • Time Complexity: O(n + m)