# Time Complexity

**Topics covered :**

1. Log Basics + Iteration Problems
2. Comparing Iterations using Graph
3. Time Complexity - Definition and Notations (Asymptotic Analysis - Big O)
6. TLE
7. Importance of Constraints

:::success
There are a lot of quizzes in this session, please take some time to think about the solution on your own before reading further.....
:::

## Basics of Logarithm

Q. What is the meaning of LOG ?
A. Logarithm is the inverse of exponential function.

Q. How to read the statement "log_b(a)"?
A. To what value we need to raise b, such that we get a.

If log_b(a) = c, then it means b^c = a.

**Examples**

1. log₂(64) = 6
**How?** 2 raise to the power what is 64? It's 6 since 2⁶ = 64

2. log₃(27) = 3
3. log₅(25) = 2
4. log₂(32) = 5

Now, calculate the floor values of the following logarithms.
5. log₂(10) = 3
6. log₂(40) = 5

**Note:**
If 2^k = N => log₂(N) = k

Let's look at one more formula:
1. What is log₂(2^6)?
A. 6
Explanation: To what power you should raise 2, such that it equates to 2^6.

2. What is log₃(3^5)?
A. 5
Explanation: To what power you should raise 3, such that it equates to 3^5.

**Note:**
In general, log_a(a^N) = N

**Question**:

Given a positive integer N, how many times do we need to divide it by 2 (Consider only integer part) until it reaches 1.

For example, N = 100
100 -> 50 -> 25 -> 12 -> 6 -> 3 -> 1
Hence, 6 times.

What if N = 324?
324 -> 162 -> 81 -> 40 -> 20 -> 10 -> 5 -> 2 -> 1
Hence, 8 times.

### **Question**
How many times we need to divide 9 by 2 till it reaches 1 ?

**Choices**
- [ ] 4
- [x] 3
- [ ] 5
- [ ] 2

**Explanation:**
N --> N/2 --> N/4 --> N/8 --> ...... 1
N/2^0 --> N/2^1 --> N/2^2 --> N/2^3 --> ...... N/2^K

N/2^K = 1
K = log₂(N)

### **Question**
How many times we need to divide 27 by 2 till reaches 1 ?

**Choices**
- [ ] 5
- [x] 4
- [ ] 3
- [ ] 6 -->

### **Question**
How many iterations will be there in this loop ?

N > 0
i = N;
while (i > 1) {
    i = i / 2;
}

**Choices**
- [ ] N
- [ ] N/2
- [ ] sqrt(N)
- [x] log(N)

**Explanation:**

The given loop starts with the initial value of i as N and continues until i becomes less than or equal to 1, by repeatedly dividing i by 2 in each iteration.

Hence, Iterations are log(N)

### **Question**
How many iterations will be there in this loop

for(i=1; i<N; i=i*2)
{ 
    ...
}

**Choices**
- [ ] infinite
- [ ] sqrt(N)
- [ ] 0
- [x] log(N)


### **Question**
How many iterations will be there in this loop ?

N>=0
for(i=0; i<=N; i = i*2)
{ 
    ...
}

**Choices**
- [x] Infinite
- [ ] N/2
- [ ] 0
- [ ] log(N)


### Question
How many iterations will be there in this loop

for(i=1; i<=10; i++){
    for(j=1; j<=N; j++){
    /     ......../
    }
}

**Choices**
- [ ] N + N
- [ ] N^2
- [x] 10 * N
- [ ] N + 10

> Multiplying the loops each time might not be correct. In this case, it works.

### **Question**
How many iterations will be there in this loop

for(i=1; i<=N; i++){
    for(j=1; j<=N; j++){
        ...
    }
}

**Choices**
- [ ] 2 * N
- [x] N * N
- [ ] 10 * N
- [ ] N * sqrt(N)

**Explanation:**

The given loop consists of two nested loops. The outer loop iterates from i=1 to i=N, and the inner loop iterates from j=1 to j=N.

For each value of i in the outer loop, the inner loop will iterate N times. This means that for every single iteration of the outer loop, the inner loop will iterate N times.

Therefore, the correct answer is N * N.

### **Question**
How many iterations will be there in this loop

for(i=1; i <= N; i++){
    for(j=1; j <= N; j = j*2){ 
        ... 
    }
}

**Choices**
- [ ] (N^2 + 2N + 1)/2
- [x] N * log(N)
- [ ] N^2
- [ ] N(N+1)/2

**Explanation:**

The given loop consists of two nested loops. The outer loop iterates from i=1 to i <= N, and the inner loop iterates from j=1 to j <= N, with j being incremented by a power of 2 in each iteration.

For each value of i in the outer loop, the inner loop iterates in powers of 2 for j. This means that the inner loop will iterate for j=1, 2, 4, 8,... up to the largest power of 2 less than or equal to N, which is log₂(N).

Therefore, the correct answer is N * log₂(N).

### **Question**
How many iterations will be there in this loop ?

for(i = 1; i <= 4; i++) {
    for(j = 1; j <= i ; j++) {
        //print(i+j)
    }
}

**Choices**
- [ ] log(N)
- [ ] 2N
- [x] 10
- [ ] N -->

### **Question**
How many Iterations will be there in this loop ?

for(i = 1; i <= N; i++) {
    for(j = 1; j <= i ; j++) {
        //print(i+j)
    }
}

**Choices**
- [ ] log(N)
- [x] N*(N+1)/2
- [ ] (N-1)/2
- [ ] N/2

### **Question**
How many iterations will be there in this loop

for(i=1; i<=N; i++){
    for(j=1; j<=(2^i); j++)
    { 
        ...
    }
}

**Choices**
- [ ] 2^N
- [x] 2 * (2^N - 1)
- [ ] 2 * (2N)
- [ ] infinite

This is GP, where a=2, r=2 and no. of terms are N.

Consider two algorithms Algo1 and Algo2 given by Kushal and Ishani respectively.

Considering **N** to be the size of the input:

Algo|Number of Iterations
-|-
Algo1|100 * log(N)
Algo2|N / 10

Now, see the graph of the two algorithms based on N.

Graphs info:

* X-axis plots N (input size)
* Red line (Algo 1): **100 * log(N)**
* Blue line (Algo 2): **N/10**


### Observations:
Assuming both graphs intersect at N = 3500, let's draw some observations.

For small input (N <= 3500), Ishani's algorithm performed better.
For large input (N > 3500), Kushal's algorithm performed better.

**In today's world data is huge**
* IndiaVSPak match viewership was **18M**.
* Baby Shark video has **2.8B** views.

Therefore, Kushal's algorithm won since it has lesser iterations for huge data value.

*We use **Asymptotic Analysis** to estimate the performance of an Algorithm when Input is huge.*

**Asymptotic Analysis** OR **Big(O)** simply means analysing perfomance of algorithms for **larger inputs**.

### Calculation of Big(O)
**Steps** for **Big O** calculation are as follows:

* Calculate **Iterations** based on **Input Size**
* Ignore **Lower Order Terms**
* Ignore **Constant Coefficients**

**Example-**
Kushal's algo took **100 * log₂N** iterations: Big O is **O(log₂N)**
Ishani's algo took **N / 10** iterations: Big O is **O(N)**

**For example**,
1. Iterations: 4N^2 + 3N + 1
2. Neglect lower order term: 3N + 1; Remaining Term: 4N^2
3. Neglect constant 4

Big O is O(N^2)

### Comparsion Order:

log(N) < sqrt(N) < N < N log(N) < N sqrt(N) < N^2 < N^3 < 2^(N) < N! < N^N

**Using an example**
N = 36
5 < 6 < 36 < 36\*5 < 36\*6 < 36² < 36³ < 2³⁶ < 36! < 36³⁶

**Ques:** What is the big notation time complexity of the following expression?
4N^2 + 3N + 6 sqrt(N) + 9 log_2(N) + 10
Ans = O(N^2)

### Question
F(N) = 4N + 3Nlog(N) + 1
O(F(N)) = ?

**Choices**
- [ ] N
- [x] N * logN
- [ ] Constant
- [ ] N^2

### Question
F(N) = 4NlogN + 3NSqrt(N) + 10^6
O(F(N)) = ?

**Choices**
- [ ] N
- [ ] N * logN
- [ ] N^2
- [x] N * Sqrt(N)

## Why do we neglect Lower Order Terms

Let's say the number of Iterations of an Algorithm are: N²+10N

N|Total Iterations = N²+10N|Lower Order Term = 10N|% of 10N in total iterations = 10N/(N²+10N)*100
-|-|-|-
10|200|100|50%
100|10⁴+10³|10³|Close to 9%
10000|10⁸+10⁵|10⁵|0.1%

## Conclusion
We can say that, as the **Input Size** increases, the contribution of **Lower Order Terms** decreases.

### Why do we neglect Constant Coefficients

When the comparison is on very larger input sizes, the constants do not matter after a certain point. For example,

| Algo 1(Nikhil)|Algo 2(Pooja)|Winner for Larger Input|
| -------- | -------- | -------- |
| 10 * log₂ N | N | Nikhil |
| 100 * log₂ N | N | Nikhil |
| 9 * N | N² | Nikhil |
| 10 * N | N² / 10| Nikhil |
| N * log₂ N | 100 * N | Pooja |

## Issues with Big(O)

### Issue 1
**We cannot always say that one algorithm will always be better than the other algorithm.**

**Example:**
* Algo1 (Iterations: 10³ N) -> Big O: O(N)
* Algo2 (Iterations: N²) -> Big O: O(N²)
* Algo 1 is better than Algo 2 but only for large inputs, not for small input sizes.

|Input Size (N)| Algo 1 (10³) | Algo 2 (N²) | Optimised|
| --| --| --| --|
|N = 10| 10⁴| 10²|Algo 2|
|N = 100| 10⁵| 10⁴|Algo 2|
|N = 10³| 10⁶| 10⁶|Both are same|
|N = 10³ + 1| (10³)*(10³ + 1)| (10³ + 1)*(10³ + 1)|Algo 1|
|N = 10⁴| 10⁷| 10⁸|Algo 1|

**Claim:** For all large inputs >= 1000, Algo 1 will perform better than Algo 2.

### Issue 2
If 2 algorithms have same higher order terms, then Big O is not capable to identify algorithm with higher iterations.

Consider the following questions -
Count the number of odd elements from 1 to N

Code 1: Iterations: N

for (int i = 1; i <= N; i++) {
    if (i % 2 != 0) {
        c = c + 1;
    }
}

Code 2: Iterations: N/2

for (int i = 1; i <= N; i = i + 2) {
    c = c + 1;
}

In both, Big O is O(N) but we know second code is better.

## Time Limit Exceeded Error

* **Is it necessary to write the entire code and then test it to determine its correctness?**
* **Can we assess the logic's viability before writing any code?**

### Online Editors and Why TLE occurs
* Codes are executed on online servers of various platforms such as Codechef, Codeforces, etc.
* The **processing speed** of their server machines is **1 GHz** which means they can perform **10⁹ instructions** per second.
* Generally, **codes should be executed in 1 second**.

Using this information, we can say at max our code should have at most **10⁹ instructions**.

Instructions means any single operation such as multiplication, addition, function calling, single variable declaration, etc.

### Question

Consider the following code:

Find the total number of instructions in the code below (Note that the instructions involved in the loop part are repetitive)


**Conclusion:**
Calculating Instructions is tedious job, rather we can make certain approximations in terms of number of Iterations.

### Approximation 1
Suppose the **code** has as small as **10 Instructions in 1 Iteration**.

Therefore,
| Instructions | Iterations |
| -------- | -------- |
| 10 | 1 |
| 10^9 | 10^8 |

In **1 sec**, we can have at max **10⁹ Instructions** or **10⁸ Iterations**, provided there are **10 Instructions / Iteration**.

### Approximation 2
Suppose the **code** has as huge as **100 Instructions in 1 Iteration**.

Therefore,
| Instructions | Iterations |
| -------- | -------- |
| 100 | 1 |
| 10^9 | 10^7 |

In **1 sec**, we can have at max **10⁹ Instructions** or **10⁷ Iterations**, provided there are **100 Instructions / Iteration**.

### Conclusion:
In general, our code can have **10⁷** to **10⁸ Iterations** to be able to run in **1 sec**.

## General Structure to solve a question

### How to approach a problem?

* Read the **Question** and **Constraints** carefully.
* Formulate an **Idea** or **Logic**.
* Verify the **Correctness** of the Logic.
* Mentally develop a **Pseudocode** or rough **Idea of Loops**.
* Determine the **Time Complexity** based on the Pseudocode.
* Assess if the time complexity is feasible and won't result in **Time Limit Exceeded (TLE)** errors.
* **Re-evaluate** the **Idea/Logic** if the time constraints are not met; otherwise, proceed.
* **Code** the idea if it is deemed feasible.

### Importance of Constraints

#### Question

If 1 <= N <= 10⁵,
then which of the following Big O will work ?

| Complexity | Iterations | Works ? |
| -------- | -------- | -------- |
| O(N³) | (10⁵)³ | No |
| O(N²) log N | (10¹⁰)*log 10⁵ | No |
| O(N²) | (10⁵)² | No |
| O(N * log N) | (10⁵)*log 10⁵ | Yes |

#### Question

If 1 <= N <= 10⁶,
then which of the following Big O will work ?

| Complexity | Iterations | Works ? |
| -------- | -------- | -------- |
| O(N³) | (10⁶)³ | No |
| O(N²) log N | (10¹²)*log 10⁶ | No |
| O(N²) | (10¹²) | No |
| O(N * log N) | (10⁶)*log 10⁶ ~ 10⁷ | May Be |
| O(N) | (10⁶) | Yes |

#### Question

If constraints are
1 <= N <= 100, N³ will also pass.

If constraints are
1 <= N <= 20, 2^N will also pass.

**Note:**
In Online Assessments, if we are not getting any other approach to a problem, try out the code; it may pass some test cases, which is better than nothing.