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

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

- Lograrithmic Time: O(log(n))

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

- Linear Time: O(n)

    for i in range(0, n, n + 3):
      pass

- Linearithmic Time: O(nLog(n))
- Quadratic Time: O(n ^ 2)

    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)

for i in range(0, 1000000000):
    pass

TC: O(n)
SC: O(1)

for i in range(0, n, c):
    pass

TC: O(log (c) n)
SC: O(1)

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

TC: O(log (2) n)
SC: O(1)

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

TC: O(log log (2) n)
SC: O(1)

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

TC: O(nlog (2) n)
SC: O(1)

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)

for i in range (n)
    pass

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