Prerequisites

Sum of first N natural numbers

1+2+3+…+N = $\frac{N*(N+1)}{2}$

Derivation

S = 1+2+3+…+(N-2)+(N-1)+N
In reverse order:
S = N+(N-1)+(N-2)+…+3+2+1
On adding:
2S = (1+N)+(2+N-1)+(3+N-2)+…+(N-2+3)+(N-1+2)+(N+1)
=> 2S = (N+1)+(N+1)+… N times
=> S = $\frac{N(N+1)}{2}$

Numbers in range [a, b]

= (b - a + 1)

Observation
Range [3, 8] = {3, 4, 5, 6, 7, 8}
=> 6 numbers
Using formula, (8 - 3 + 1) = 6

Number of factors of a number N

For N=12: Iterate from $[1, 12]$ and check for factor of 12.

flowchart TD
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12

    style 1 fill:lightgreen
    style 2 fill:lightgreen
    style 3 fill:lightgreen
    style 4 fill:lightgreen
    style 5 fill:pink
    style 6 fill:lightgreen
    style 7 fill:pink
    style 8 fill:pink
    style 9 fill:pink
    style 10 fill:pink
    style 11 fill:pink
    style 12 fill:lightgreen

Total number of factors = {1, 2, 3, 4, 6, 12} = 6

    Execution Time
    
Time for execution of a code. Depends on external factors.

Need for optimization

Let’s assume CPU can perform $10^8$ iterations in 1 second.
=> For $10^{18}$ iterations, it will take $\frac{10^{18}}{10^8}$seconds = $10^{10}$seconds $\approx$ 317 years.
This is an impractical amount of time.

Optimizations:

Observation
if i is a factor of N, it means for some j,
$i*j = N$ {both i and j are factors of N}
$=> j = \frac{N}{i}$

$=> i*i \leq N$
$=> i \leq \sqrt{N}$

Iteration needs to be done for range $[1, \sqrt{N}]$.

Hence, time taken for $N = 10^18$ iterations:
$\frac{\sqrt{10^{18}}}{10^8}$ seconds.
$= 10 $seconds.

Time Complexity

Program 1:

int i = n;
while(i > 1) {
    i = i / 2;
}

Value of $i$ for N = 100.

flowchart TD
    100 --> 50
    50 --> 25
    25 --> 12
    12 --> 6
    6 --> 3
    3 --> 1

    N --> N/2
    N/2 --> N/4
    N/4 --> N/8
    N/8 --> N/16
    N/16 --> ...
    ... --> ONE[1]

Let number of iterations be $k$.
$N = 2^k$ $=> log_2(N) = k$

Program 2:

for(int i = 1; i<= N; i++) {
    for(int j = 1; j<=N; j++) {
        System.out.println(i+j);
    }
}

Hence, total number of iterations = $N*N = N^2$

Program 3:

for(int i = 0; i < n; i++) {
    for(int j = 0; j < i; j++) {
        System.out.println(i+j);
    }
}

Total number of iterations = $1+2+3+…+(N-1)$ = $\frac{(N-1)*N}{2}$ = $\frac{N^2}{2} - \frac{N}{2}$

Big O Complexity

Steps:

1. Find number of iterations.
2. Ignore lower order terms.
3. Ignore coefficients.

Eg: Big O Complexity of last problem is $O(N^2)$.

Why we ignore lower order terms?

Eg: No. of iterations = $N^2 + 10N$

Therefore, as value of N increases, contribution of lower order terms reduces. For large N, the contribution is almost 0. That’s why the lower order terms and coefficients are ignored when calculating Big O Notations.

Bitwise Operations