Scribd
Upload
16 views3 pages

Algorithm Complexities and NP Classifications

The document outlines various algorithm complexities and NP classifications, detailing specific problems such as Subset Sum, Traveling Salesman Problem, and Vertex Cover, along with their respective complexities. It also categorizes different types of algorithms including string matching, search, sorting, graph, geometric problems, and dynamic programming, providing their time complexities. Additionally, it covers number theory algorithms and their efficiencies.

Uploaded by

gaurmohit2120076
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
16 views3 pages

Algorithm Complexities and NP Classifications

The document outlines various algorithm complexities and NP classifications, detailing specific problems such as Subset Sum, Traveling Salesman Problem, and Vertex Cover, along with their respective complexities. It also categorizes different types of algorithms including string matching, search, sorting, graph, geometric problems, and dynamic programming, providing their time complexities. Additionally, it covers number theory algorithms and their efficiencies.

Uploaded by

gaurmohit2120076
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

Algorithm Complexities & NP Classifications

NP Classification

NP-Hard / NP-Complete Problems:

1. Subset Sum (DP-based): O(n * S) - Pseudo-polynomial, NP-Complete

2. Traveling Salesman Problem (TSP): O(n!) - NP-Hard

3. Vertex Cover: NP-Complete

4. Set Cover: NP-Complete, Approximation ratio O(log n)

5. Bin Packing: NP-Hard, Brute-force O(n!)

6. Hamiltonian Circuit: O(n!) - NP-Complete

7. Assignment Problem: O(n^3) - Solvable in P (Hungarian Algorithm)

Algorithm Complexities

String Matching Algorithms:

- Naïve: O(n * m)

- Rabin-Karp: Average O(n + m), Worst O(n * m)

- KMP: O(n + m)

Search Algorithms:

- Binary Search: Best O(1), Average/Worst O(log n)

- Linear Search: Best O(1), Average/Worst O(n)

Sorting Algorithms:

- Merge Sort: O(n log n)

- Quick Sort: Best/Average O(n log n), Worst O(n^2)

- Insertion Sort: Best O(n), Average/Worst O(n^2)

- Selection Sort: O(n^2)

- Bubble Sort: Best O(n), Average/Worst O(n^2)

- Counting Sort: O(n + k)

- Radix Sort: O(n * d)


Algorithm Complexities & NP Classifications

- Bucket Sort: Average O(n + k), Worst O(n^2)

- Heap Sort: O(n log n)

Math & Matrix:

- Large Integer Multiplication: Karatsuba O(n^1.585), FFT O(n log n)

- Strassen's Matrix Multiplication: O(n^2.81)

- Binomial Coefficient (DP): O(n * k)

- Matrix Chain Multiplication: O(n^3)

Graph Algorithms:

- DFS/BFS: O(V + E)

- Connected Components: O(V + E)

- Topological Sort: O(V + E)

- Warshall's Algorithm: O(n^3)

- Floyd-Warshall: O(n^3)

- Dijkstra's (Heap): O((V + E) log V)

- Prim's (Heap): O((V + E) log V)

- Kruskal's: O(E log E)

- Huffman Coding: O(n log n)

- Single-Source Shortest Path: Depends on method (e.g., Dijkstra)

- All-Pairs Shortest Path: O(n^3)

Geometric Problems:

- Closest-Pair (Naive): O(n^2)

- Closest-Pair (D&C): O(n log n)

- Convex Hull (Graham Scan): O(n log n)

- Voronoi Diagram: O(n log n)

Data Structures & Transform and Conquer:

- Balanced BST Ops: O(log n)

- Heap Insert/Delete: O(log n)

- Hash Table (Chaining): Average O(1), Worst O(n)


Algorithm Complexities & NP Classifications

Dynamic Programming & Greedy:

- 0/1 Knapsack: O(n * W)

- Longest Common Subsequence: O(m * n)

- Optimal BST: O(n^3)

Number Theory:

- Modular Arithmetic: O(1)

- GCD (Euclidean): O(log n)

- Chinese Remainder Theorem: O(k log n)

You might also like