Scribd
Upload
5 views1 page

Time Complexity Overview in DSA

The document provides a general time complexity table in data structures and algorithms (DSA), detailing various complexities such as constant, logarithmic, linear, linearithmic, quadratic, cubic, exponential, and factorial time. Each complexity is accompanied by examples from DSA, scenarios in which they occur, and real-life analogies for better understanding. This serves as a quick reference for understanding the efficiency of different algorithms based on their time complexity.

Uploaded by

sai prashanna
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views1 page

Time Complexity Overview in DSA

The document provides a general time complexity table in data structures and algorithms (DSA), detailing various complexities such as constant, logarithmic, linear, linearithmic, quadratic, cubic, exponential, and factorial time. Each complexity is accompanied by examples from DSA, scenarios in which they occur, and real-life analogies for better understanding. This serves as a quick reference for understanding the efficiency of different algorithms based on their time complexity.

Uploaded by

sai prashanna
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

⚡ General Time Complexity Table in DSA

(Extended)

Time
Name Example in DSA When It Happens Real-Life Analogy
Complexity

Accessing array Operation doesn’t


Constant Picking the first book
O(1) element, Hash map depend on input
Time from a shelf 📚
lookup, Stack push/pop size

Binary Search, Balanced


Logarithmic Input size reduces Finding a word in a
O(log n) BST search, Heap
Time by half each step dictionary 📖
operations

Traversing array, Linear Every element


Taking attendance in a
O(n) Linear Time Search, BFS/DFS in needs to be
class 🏫
graph checked once

Merge Sort, Quick Sort Efficient divide-


Linearithmic Sorting names in a
O(n log n) (avg), Heap Sort, Tree and-conquer
Time phonebook 📒
Sort algorithms

Bubble Sort, Selection Comparing every


Quadratic Nested loops over
O(n²) Sort, Insertion Sort student with every
Time entire input
(worst case) other student 👩‍🎓👨‍🎓

Checking all seat


Matrix multiplication Triple nested
O(n³) Cubic Time combinations in a hall
(naïve), 3 nested loops iterations
🎭

Recursive Fibonacci, Trying every


Exponential Branching doubles
O(2^n) Travelling Salesman combination of
Time with each input
(subset method) clothes 👕👖

When every
Travelling Salesman Shuffling and
Factorial possible
O(n!) (brute force), generating checking every order
Time order/arrangement
permutations of a deck of cards 🃏
is tried

Page 1 of 1

You might also like