Scribd
Upload
13 views2 pages

Time Complexity

The document summarizes the time complexities of various algorithms categorized into Divide & Conquer, Greedy Methods, Dynamic Programming, Backtracking, and Branch & Bound. It provides best, average, and worst-case time complexities for each algorithm, highlighting key algorithms such as Binary Search, Quick Sort, and the Travelling Salesperson Problem. Additionally, it notes that NP-Hard and NP-Complete problems typically require exponential time unless P = NP.

Uploaded by

syednehanazmeensyedneha
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
13 views2 pages

Time Complexity

The document summarizes the time complexities of various algorithms categorized into Divide & Conquer, Greedy Methods, Dynamic Programming, Backtracking, and Branch & Bound. It provides best, average, and worst-case time complexities for each algorithm, highlighting key algorithms such as Binary Search, Quick Sort, and the Travelling Salesperson Problem. Additionally, it notes that NP-Hard and NP-Complete problems typically require exponential time unless P = NP.

Uploaded by

syednehanazmeensyedneha
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
You are on page 1/ 2

Time Complexity Summary

1 Divide & Conquer and Greedy Method

Algorithm/Problem Best Case Average Worst Case


Case
Binary Search O(1) O(log n) O(log n)
Quick Sort O(n log n) O(n log n) O(n2 )
Merge Sort O(n log n) O(n log n) O(n log n)
Strassen’s Matrix Multiplication O(n2.81 ) O(n2.81 ) O(n2.81 )
Job Sequencing with Deadlines O(n log n) O(n log n) O(n log n)
(Greedy)
Fractional Knapsack (Greedy) O(n log n) O(n log n) O(n log n)
Minimum Cost Spanning Tree O(E + log V ) O(E log V ) O(E log V )
(Prim/Kruskal)

2 Dynamic Programming and Backtracking

Algorithm/Problem Best Case Average Worst Case


Case
Optimal Binary Search Tree O(n2 ) O(n2 ) O(n2 )
Matrix Chain Multiplication O(n3 ) O(n3 ) O(n3 )
0/1 Knapsack (DP) O(nW ) O(nW ) O(nW )
All Pairs Shortest Path (Floyd- O(n3 ) O(n3 ) O(n3 )
Warshall)
Travelling Salesperson Problem (DP) O(n2 · 2n ) O(n2 · 2n ) O(n2 · 2n )
N-Queen (Backtracking) O(N !) - O(N !)
Sum of Subsets (Backtracking) O(2n ) - O(2n )
Graph Coloring (Backtracking) O(mn ) - O(mn )
Hamiltonian Cycle (Backtracking) O(n!) - O(n!)

3 Branch & Bound and P, NP, NP-Hard, NP-Complete

Algorithm/Problem Best Case


Average Worst Case
Case
Travelling Salesperson (Branch and Depends on O(n!) O(n!)
Bound) pruning

1
0/1 Knapsack (LC/FIFO Branch and Depends on O(2n ) O(2n )
Bound) pruning
Clique Decision Problem NP- - -
Complete

Note
• For NP-Hard and NP-Complete problems, exact time complexities are not defined,
and they generally require exponential time unless P = NP.

• “Depends on pruning” indicates that branch-and-bound performance heavily de-


pends on how effectively the algorithm can prune the search space.

You might also like