deathook007/Data-Structures-and-Algorithms

Best DSA Questions Repository for Begineers to Intermidiate in C++

C++

Complexity Analysis 📈

Linear Search

Time complexity : O(n)
Space complexity : O(1)

Binary Search

Time complexity : O(log(n))
Space complexity :
```
Itterative version - O(1)
```
```
Recursive version - O(n)   
```

Binary search works on monotonic functions (non-increasing or non-decreasing)

Jump Search

Time complexity : O(√n)
Space complexity : O(1)

Interpolation Search

Time complexity : O(log(log(n)))
Space complexity : O(1)

Time Complexity increases with the increase in non uniformity of data. For uniformily distributed data Interpolation Search is better than Binary Search while it keeps on changing as uniformity of data changes and go upto O(n), while in case of Binary search its O(log(n)) dispite of how data is distributed in shorted array. Here is the average complexity considering most data to be uniform.

Exponential Search

Time complexity : O(log(n))
Space complexity :
```
Itterative version - O(1)
```
```
Recursive version - O(n) 
```

Time Complexity depends on binary search only not exponential searcch(O(1)). The Exponential Search is better than Binary Search in every case specially for UNBOUNDED ARRAYS

Fibonacci Search

Time complexity : O(log(n))
Space complexity : O(1)

Bubble Sort

Time complexity : O(n²)
Space complexity : O(1)

Insertion Sort

Time complexity : O(n²)
Space complexity : O(1)

Selection Sort

Time complexity : O(n²)
Space complexity : O(1)

Inbuilt Sort

Time complexity : O(n)
Space complexity : O(1)

Counting Sort

Time complexity : O(n + Range) ~ O(n)
Space complexity : O(Range)