---
# System prepended metadata

title: Analysis of Algorithms
tags: [Data Structures & Algorithms, GeeksforGeeks]

---

# Analysis of Algorithms 
- helps to compare performance of algorithms 
- Asymptotic Analysis - Theroritical analysis of algorithm 
    - measure the order of growth based on input size
    - does not depend of machine, programming language etc
    - no need to implement, we can analyze algorithm 

### Asumtotic analysis 
- all constant operations takes constant time 


### Complexity Analysis
- How much time - Time complexity
- How much space - Space Compleixty

### Big O Notation
- upper bound of complexity in worst case for large input size

### Complexities
- Constant Time O(1)
- Log Lograrithmic Time: O(log log(n))
  ``` python
  for i in range(0, n, n ^ 2):
      pass
  ```
- Lograrithmic Time: O(log(n))
  ``` python
  for i in range(0, n, n * 2):
      pass
  ```
- Linear Time: O(n)
    ``` python
    for i in range(0, n, n + 3):
      pass
    ```
- Linearithmic Time: O(nLog(n))
- Quadratic Time: O(n ^ 2)
    ``` python
    for i in range(n):
        for i in range(n):
          pass
    pass
    ```
- Cubic Time: O(n ^ 3)
- Exponential Time: O(b ^ n), b > 1
- Factorial Time: O(n!)

```
O(1) < O(log log(n)) < O(log(n)) < O(n) < O(nlog(n)) < O(n ^ 2) < O(n ^ 3) < O(b ^ n) < O(n!) 
```

### Problem Complexities 
- Prime factorization of an integer, or checking primality or compositeness of an integer naively: O(sqrt(n))
- Iterating through all subsets of size k of the input elements: O(n^k). For example, iterating through all triplets is O(n^3).
- Iterating through all subsets: O(2^n)
- Iterating through all permutations: O(n!)
- Sorting using Merge sort - O(nlog(n))
- Java Quick Sort - O(n ^ 2)
- Iterating matrix - O(mn)


### Other concepts
- P vs NP - Polynomial Time vs Non Deterministic Polynomial Time problems (exponential time O(2 ^ n and more))
- NP Complete Problems 


Ad-hoc problems are problems that don’t fall into any standard algorithmic category
with well known solutions


### Amortized Analysis
estimate the total time used to all such operations during the execution of the algorithm, instead of focusing on individual operations.


What does it mean when we say that an algorithm X is asymptotically more efficient than Y?
- X will always be a better choice for large inputs


### Analsysis of Loops

TC: O(1)
SC: O(1)
``` python
for i in range(0, 1000000000):
    pass
```

TC: O(n)
SC: O(1)
``` python
for i in range(0, n, c):
    pass
```

TC: O(log (c) n)
SC: O(1)
``` python
for i in range(0, n, i * c):
    pass
```

TC: O(log (2) n)
SC: O(1)
``` python
for i in range(0, n, i * 2):
    pass
```

TC: O(log log (2) n)
SC: O(1)
``` python
for i in range(0, n, i ** 2):
    pass
```


TC: O(nlog (2) n)
SC: O(1)
``` python
for i in range (n)
    for i in range(0, n, i * 2):
        pass
```


TC: O(log (2) n) + O(n) -> O(n)
SC: O(1)
``` python
for i in range (n)
    pass

for i in range(0, n, i * 2):
    pass
```


                                           
                                           
                                    