sansh2356 / ada_new

Analysis and Design of Algorithm Lab

Welcome to the Analysis and Design of Algorithm Lab repository! In this lab, we explore various algorithms and analyze their time and space complexities. This repository contains implementations and analyses of the following algorithms:

1)Quicksort
2)Iterative Quicksort
3)Finding Pivot Element
4)Merge Sort
5)Counting N Numbers (Iteratively and Recursively)
6)Activity Selection Problem
7)Knapsack Problem
8)Dijkstra's Algorithm
9)Kruskal's Algorithm
10)Prim's Algorithm
11)Multi-Staged Graph
12)Selection Sort
13)Magic Square
15)Recursive Matrix Multiplication
16)Min-Max of an Array using Divide and Conquer Approach
Each algorithm has been analyzed with respect to its time and space complexities, allowing for a deeper understanding of their performance characteristics and suitability for various applications.

Feel free to explore each algorithm's analysis to gain insights into their efficiency and applicability.

Quicksort

Time Complexity: Best Case: O(n log n) Worst Case: O(n^2) Average Case: O(n log n) Space Complexity: O(log n)

Iterative Quicksort

Time Complexity: Same as Quicksort Space Complexity: Same as Quicksort

Finding Pivot Element

Time Complexity: Best Case: O(n) Worst Case: O(n) Space Complexity: O(1)

Merge Sort

Time Complexity: Best Case: O(n log n) Worst Case: O(n log n) Average Case: O(n log n) Space Complexity: O(n)

Counting N Numbers (Iteratively and Recursively)

Time Complexity: O(n) for both iterative and recursive implementations Space Complexity: Iterative: O(1) Recursive: O(n) due to recursive calls

Activity Selection Problem

Time Complexity: O(n log n) Space Complexity: O(1) Knapsack Problem

Time Complexity: O(nW), where n is the number of items and W is the capacity of the knapsack Space Complexity: O(nW)

Dijkstra's Algorithm

Time Complexity: O(V^2) using adjacency matrix O((V + E) log V) using priority queue with adjacency list Space Complexity: O(V^2) using adjacency matrix O(V + E) using adjacency list

Kruskal's Algorithm

Time Complexity: O(E log E), where E is the number of edges Space Complexity: O(V + E), where V is the number of vertices and E is the number of edges

Prim's Algorithm

Time Complexity: O(V^2) using adjacency matrix Space Complexity: O(V + E) using adjacency list

Multi-Staged Graph

Time Complexity: Depends on the specific algorithm used for traversal or solving problems related to multi-staged graphs. Space Complexity: Depends on the specific algorithm used.

Selection Sort

Time Complexity: Best Case: O(n^2) Worst Case: O(n^2) Space Complexity: O(1)

Magic Square

Time Complexity: Depends on the specific algorithm used for generating or solving magic squares. Space Complexity: Depends on the specific algorithm used.

Recursive Matrix Multiplication

Time Complexity: Depends on the specific algorithm used for matrix multiplication. Space Complexity: Depends on the specific algorithm used.

Min-Max of an Array using Divide and Conquer Approach

Time Complexity: O(n) Space Complexity: O(log n)