Undertanding enough Time complexity

I know it sometimes can get tricky to calculate the time complexity of an algorithm as a beginner, and the proofs behind that time complexity can be daunting. In this blog let's understand time complexity in a much simpler way (also just enough to get you up to speed).

Let's first understand What time complexity is, what it denotes and why we need it.

In the end, we all want our algorithms to take as little time as possible. However, calculating time with a stopwatch is an incorrect criterion for judging an algorithm. Let's understand why with a couple of examples:-
consider Tushar wrote algo1 and Arun wrote algo2.
1. algo1 took 2min to run while alog2 took 3min.
Our first intuition will be ohh! alog1 is better.
But what If I told you algo1 was running on a Mac machine and algo2 on a Windows machine and when algo2 ran on Mac, it also took 2 min.
2. Consider again the same example but a different algo and this time both using the same machine. Now algo1 is taking 3min and algo2 is taking 2min.
So algo2 is better?
What if I tell you that algo1 was written in Python and algo2 was written in C++?

With the above examples, we can see that time might not be the best possible entity to analyze an algorithm as it depends on various factors like machine specs, programming language, etc.

So we need something constant which will not depend on any factors.
Here comes the ITERATIONS.
We can calculate the number of iterations an algorithm is taking.

In the following example, the algorithm is taking N iterations and whatever the specs may be it'll always take N iterations.

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

So basically Time complexity is denoting the number of iterations based on the input that we're getting.

Now comes the question, why do we need it? let me explain with an example.

Suppose you are given a number and you are asked to write a program to count the number of factors.
Let's first consider a brute-force approach.

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

In the above program, N inputs will take N iterations.
let's take an assumption that when N will be 10^8, our program will take 1 second.

So when N is 10^18 our program will take 10^10 seconds.
Can you guess how much is that time?
IT IS EQUIVALENT TO APPROXIMATELY 316 YEARS!!!

Which is way too much, let's see if we can optimize the program with an observation.

Consider N is 24.
We can also represent a factor in the form of i * N/i, let's use this to make a table of factors as shown below

In the above table, all the i values are the factors of 24.
But did you notice something?
If we know i, we can calculate N/i and get the 2nd factor.
Also, after a certain iteration, i is just repeating the values of N/i.

Now we just need to find at what point factors repeat.
If you look closely, i repeat as N/i when i become greater than N/i.
so we need to run our loop until i<=N/i, which is nothing but i*i<=N.

Our revised solution will look like this

int count=0;
for(int i=1; i*i<=N; i++){
    /*consider N=100, so when i becomes 10, N/i will also be 10,
    in this case we only need to increment the count by 1.*/
    if(i*i==N){
        count++;
    }else if(N%i==0){
        count+=2;
    }
}

i*i<=N can also be written as i<=SquareRoot(N)
So now if N is 10^18, the iterations will be 10^9,
and 10^8 is 1 second so 10^9 will take 10 seconds.

With this optimization, we reduced the time taken by the algorithm from 316 years to merely 10 seconds.

This is why we need Time complexity to analyze and optimize the code, as it creates a huge difference in large input sizes.

So now we understand the importance of it, It's time we dive into some examples but before that let's keep in mind following mathematical formalae.

Arithmetic Progression
Sum of first N natural numbers = (N*(N+1))/2

Geometric Pogression
Its a sequence which has common ratio multiplication.
for eg:- 2,4,8,16,32...
Here common ratio is 2 and next term can be obtained by multiplying common ratio 2 to current number.
Generic notation will be
a, ar^2, ar^3, ar^4...
sum of such sequence is (a*(r^n-1))/(r-1)

Logarithm

$$log_2n=k$$

Above expression means 2^k = n.
Its useful to calculate number of iterations if a number is getting halved till it reached 1.
something like following
9 -> 4 -> 2 -> 1
its getting halved at every stage. (for odd we're considering floor values).
Generalizing it, we'll get
N/(2^0) -> N/(2^1) -> N/(2^2) -> N/(2^k)
If we get this value of k we'll get number of iterations
Also in above expression we know that
N/(2^k) = 1
which is N = 2^k
to get value of k, we can use log

$$k=log_2N$$

Above is how we can get number of iterations for a number which is getting halved at every iteration.

Lets see some examples:-

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

   As above loop which run in following way
   N -> N/2 -> N/4... -> 1
   So its number of iterations can be found out using log2n
   Therefore it Time complexity will be Log2n.

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

   Above code will run like following

   | Instance | Iterations | | --- | --- | | 1st instance | 1 | | 2nd instance | 2 | | 3rd instance | 3 | | Nth instance | N |

   So total iterations will be 1+2+3..N, which is nothing but AP
   so here TC will be N*(N+1)/2.

BigO Notation

To put it simply, It is used to denote algorithmic performance for larger inputs.
For larger inputs, we can ignore the constants and lower order terms in number of iterations we calculated.
for eg:-
If number of iterations of some algorithm is 2N^2 + 4N + 1
Here we can ignore 4 and 1 as its constants
then we can ignore N as well, as its a lower order term.
So its BigO will be BigO(N^2).

The simple reason behind this is, as N gets bigger, other values won't contribute to the overall time as much as N^2 will, that's why BigO ignores constants and lower order terms.

In our previous AP example, the number of iterations was N*(N+1)/2.
Its BigO will be BigO(N^2).

This is enough to get you started with calculating Time complexities of different algorithms when you're starting your DSA journey.
Feel free to dive into details and proofs behind these if curious.
Thank you for reading it through.