Scribd Logo
Upload

Welcome to Scribd!

  • 32 views

    Know Thy Complexities!: Big-O Complexity Chart

    Uploaded by

    Rhythm Patel
    The document provides a summary of common data structures and their time and space complexities. It includes a big-O complexity chart and tables summarizing the average, worst-case time complexities of common operations like access, search, insertion, and deletion for various data structures including arrays, stacks, queues, linked lists, hash tables, trees, and more. It also includes a table summarizing the time and space complexities of common sorting algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Know Thy Complexities!: Big-O Complexity Chart

    Uploaded by

    Rhythm Patel
    32 views2 pages
    The document provides a summary of common data structures and their time and space complexities. It includes a big-O complexity chart and tables summarizing the average, worst-case time complexities of common operations like access, search, insertion, and deletion for various data structures including arrays, stacks, queues, linked lists, hash tables, trees, and more. It also includes a table summarizing the time and space complexities of common sorting algorithms.

    Original Description:

    Big O Cheatsheet - Algorithms

    Original Title

    Big O Cheatsheet

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document provides a summary of common data structures and their time and space complexities. It includes a big-O complexity chart and tables summarizing the average, worst-case time complexities of common operations like access, search, insertion, and deletion for various data structures including arrays, stacks, queues, linked lists, hash tables, trees, and more. It also includes a table summarizing the time and space complexities of common sorting algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    32 views2 pages

    Know Thy Complexities!: Big-O Complexity Chart

    Uploaded by

    Rhythm Patel
    The document provides a summary of common data structures and their time and space complexities. It includes a big-O complexity chart and tables summarizing the average, worst-case time complexities of common operations like access, search, insertion, and deletion for various data structures including arrays, stacks, queues, linked lists, hash tables, trees, and more. It also includes a table summarizing the time and space complexities of common sorting algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    Know Thy Complexities!

    www.bigocheatsheet.com

    Big-O Complexity Chart


    Horrible Bad Fair Good Excellent

    O(n!) O(2^n)
    O(n^2)

    O(n log n)
    Operations

    O(n)

    O(log n), O(1)


    Elements
    Common Data Structure Operations
    Data Structure Time Complexity Space Complexity
    Average Worst Worst
    Access Search Insertion Deletion Access Search Insertion Deletion
    Array Θ(1) Θ(n) Θ(n) Θ(n) O(1) O(n) O(n) O(n) O(n)

    Stack Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n)

    Queue Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n)

    Singly-Linked List Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n)

    Doubly-Linked List Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n)

    Skip List Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n log(n))

    Hash Table N/A Θ(1) Θ(1) Θ(1) N/A O(n) O(n) O(n) O(n)

    Binary Search Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)

    Cartesian Tree N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(n) O(n) O(n) O(n)

    B-Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

    Red-Black Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

    Splay Tree N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(log(n)) O(log(n)) O(log(n)) O(n)

    AVL Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

    KD Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)

    Array Sorting Algorithms


    Algorithm Time Complexity Space Complexity
    Best Average Worst Worst
    Quicksort Ω(n log(n)) Θ(n log(n)) O(n^2) O(log(n))

    Mergesort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(n)

    Timsort Ω(n) Θ(n log(n)) O(n log(n)) O(n)

    Heapsort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(1)

    Bubble Sort Ω(n) Θ(n^2) O(n^2) O(1)

    Insertion Sort Ω(n) Θ(n^2) O(n^2) O(1)

    Selection Sort Ω(n^2) Θ(n^2) O(n^2) O(1)

    Tree Sort Ω(n log(n)) Θ(n log(n)) O(n^2) O(n)

    Shell Sort Ω(n log(n)) Θ(n(log(n))^2) O(n(log(n))^2) O(1)

    Bucket Sort Ω(n+k) Θ(n+k) O(n^2) O(n)

    Radix Sort Ω(nk) Θ(nk) O(nk) O(n+k)

    Counting Sort Ω(n+k) Θ(n+k) O(n+k) O(k)

    Cubesort Ω(n) Θ(n log(n)) O(n log(n)) O(n)

    You might also like