Scribd
Upload
40 views2 pages

DAA - Time Complexities of Algorithms

The document outlines various algorithmic approaches along with their associated problems and time complexities. It categorizes methods into Divide and Conquer, Dynamic Programming, Greedy Method, Backtracking, and Branch and Bound, detailing their performance in best, average, and worst-case scenarios. Key algorithms discussed include Binary Search, Quick Sort, and the Travelling Salesperson Problem, among others.

Uploaded by

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

DAA - Time Complexities of Algorithms

The document outlines various algorithmic approaches along with their associated problems and time complexities. It categorizes methods into Divide and Conquer, Dynamic Programming, Greedy Method, Backtracking, and Branch and Bound, detailing their performance in best, average, and worst-case scenarios. Key algorithms discussed include Binary Search, Quick Sort, and the Travelling Salesperson Problem, among others.

Uploaded by

saibabusaibabu906
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

[Link].

Approach Problems Time Complexity


1 Divide and Binary Search Successful :
Conquer Best - O(1)
Avg - O(log n)
Worst - O(log n)
Unsuccessfull :
Best, Avg, Worst-O(log n)

Quick Sort Best - O(nlog n)


Avg - O(nlog n)
Worst - O(n^2)

Merge Sort Best - O(nlog n)


Avg - O(nlog n)
Worst - O(nlog n)

Strassen’s matrix O(n^log2(7)) ≅ O(n^2.81)


Multiplication
2 Dynamic Optimal binary O(n^3)
Programming search trees
All pairs shortest O(n^3)
path problem

0/1 knapsack O(n*w) ,Where


problem n = number of items
available
w = capacity of the knapsack

Travelling O(2^n * n^2)


salesperson problem

Optimal rod cutting Top down approach -


O(n^2)
Bottom up approach -
O(n^2)
[Link] Approach Problems Complexity
3 Greedy Job sequencing with O(2^n)
Method deadlines problem
Fractional knapsack O(nlog n)
problem
Minimum cost spanning Prim’s Algorithm :
trees
Adjacency Matrix - O(n^2)
Adjacency List -
O(log n)
Kruskal’s Algorithm :
O(log n)
Single source shortest O(n^2)
paths problem

Activity selection Unsorted – O(nlog n)


problem
Sorted – O(n)
4 Backtracking n-queens problem O(n!)
sum of subsets problem O(2^n)

Hamiltonian cycles O(n!)

5 Branch and Travelling sales person Worst Case - O(n!)


Bound problem with LCBB
0/1 knapsack problem : LC branch and bound :
1. LC branch and Worst Case - O(2^n)
bound solution.
Average Case -O(nlog n)
2. FIFO branch and
bound solution FIFO branch and bound:
O(2^n)

You might also like