Data-Structures-and-Algorithms

KO | EN

gitlite — search

#python #javascript #react #typescript #hacktoberfest #c #vue #statistics #automation #django #nlp #docker

Data-Structures-and-Algorithms

★ 20 Open GitHub ↗

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

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

![Screenshot-1](https://github.com/deathook007/DSA-and-Coding-Practice/blob/master/Data%20Structures%20and%20Algorithms.jpeg)

# Complexity Analysis 📈

![Screenshot-1](https://github.com/deathook007/DSA-and-Coding-Practice/blob/master/Time%20complex.png)

### 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)

Data-Structures-and-Algorithms

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README