Scribd
Upload
4 views1 page

Time Complexity of Algorithms Explained

The document outlines the time complexity of various algorithms, including Selection Sort, Quick Sort, and Prim's Algorithm, detailing their best, average, and worst-case scenarios. It highlights that Selection Sort has a time complexity of O(n²) in all cases, while Quick Sort can degrade to O(n²) in the worst case. Additionally, it covers algorithms like the Floyd-Warshall and 0/1 Knapsack, emphasizing their complexities in relation to input size and structure.

Uploaded by

rajatslad05
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
4 views1 page

Time Complexity of Algorithms Explained

The document outlines the time complexity of various algorithms, including Selection Sort, Quick Sort, and Prim's Algorithm, detailing their best, average, and worst-case scenarios. It highlights that Selection Sort has a time complexity of O(n²) in all cases, while Quick Sort can degrade to O(n²) in the worst case. Additionally, it covers algorithms like the Floyd-Warshall and 0/1 Knapsack, emphasizing their complexities in relation to input size and structure.

Uploaded by

rajatslad05
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

Time Complexity of Common Algorithms

Algorithm Best Case Average Case Worst Case Notes


Selection Sort O(n²) O(n²) O(n²) Not adaptive; independent of input order

Quick Sort O(n log n) O(n log n) O(n²) Worst case when pivot selection is poor

Fractional Knapsack O(n log n) O(n log n) O(n log n) Sorting items by value/weight ratio

Prim’s Algorithm O(E + V log V) - O(E + V log V) Using Min Heap / priority queue

Longest Common Subsequence (LCS)


O(m × n) O(m × n) O(m × n) m, n = lengths of two sequences

Floyd–Warshall Algorithm O(V³) O(V³) O(V³) All-pairs shortest path algorithm

0/1 Knapsack (DP) O(n × W) O(n × W) O(n × W) W = capacity of knapsack

You might also like