Time Complexity | DSA 001
Tags: python, programming, beginners, tutorial
Published: 2022-08-19 01:30:40

## Ways to calculate code performance

### Approach 1: Time based approach

```
calculateTime()
function fancyName(){
   do something
}
calculateTimeDifference()
```

In this approach of judging code, before running a chunk of code, the initial time is taken and after running that code, the final time is taken. Then when the final time is subtracted from initial time, we get the how much time was required for processing of the code. 

This method of calculating code performance is rated as average but still this approach is used hugely to judge code

#### Problems in Approach 1:
- It is based on machine: Depends from processor to processor
- It is based on processing: Depends on the processing power of your PC

### Approach 2:
Counting the number of operations in a code. Technically, this literally means that we are going to count the number of operations in a code.

**Count Operation in the code below**
`a = a + 1`

If you said there is one operation, you are wrong my friend. There are actually 2 operator: "=" and "+"

Now, count the operation in this code
```
sum = 0
winner = 1
for (i = 1; i < n; i++){
  sum = sum+1
}
```

Notice closely, that there are several operators. In total, there is 3 "="s, 1 "<", then in `i++`, there are actually 2 operators which are responsible to increment the value of i, `i++` can be written as `i = i+1`, so in `i++` there are 2 operators. Then inside the loop there are 2 operators: "=" and "+"

But, in this code, apart from `sum = 0`, `winner = 1`, `i=1`, all the other operators are dependent on the variable `n`. So, there are 3 constant operators, and 5 operators which varies with the value of `n`. Thus there are 3+5n operators

## Big O
The whole way of measuring code with number of operators is known as Big O. 

**Code 1**
```
sum = 0
i = 0
while (i < n):
    sum += i
    i += 1
print(sum)
```

In this given code, there are 5n+2 operators. 

Now, coming to the complexity of the code: To measure the complexity of the code, the constants are to be ignored. 

So O(n) [Said as O of n] is the complexity

**Code 2**
```
for (------):
  ---------
  ---------
for (------):
  ---------
  ---------
```

You might think that the complexity of the above code is 2O(n) and that's completely correct. But since the constants are to be ignored, so the complexity will be O(n).

**Code 3**
```
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    sum+=j
  }
}
```
In the above code, O(n) is inside another O(n). Thus, the complexity of the code becomes O(n^2). If the nested loop would run on a constant and not on N, the complexity would not be O(n^2). 

### Complexity Notation
| Code Complexity  | Notation | Note |
| ------------- |:-------------:|:-------|
| O(10), O(1000) O(k), 3O(k) kO(k)  | O(1)     | "k" is some constant |
| O(3n), O(4n+100000)      | O(n)| Constants are to be ignored |
| O(3n^2), O(4n^2+100000)       |  O(n^2)   | Constants are to be ignored |
| O(3n^2), O(4n^2 + 3n + 4)       |  O(n^2)   | Since with increasing value of n, the value of n^2 will become much higher than theat of n, so n can be ignored, incase of cubic equations,the complexity will be O(n^3) and so on |


![Complexity time graph](https://miro.medium.com/max/1400/1*yiyfZodqXNwMouC0-B0Wlg.png)

This graph shows the time for complexity of code with increasing input.