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)