What is time complexity?

By definition, the Time complexity is the time taken by an algorithm/program to run as a function of the length of the input.

It's important to know that time complexity doesn't actually measure the time taken by an algorithm to run. Because that kind of depends on the programming language, processing power, etc. It calculates the execution time of an algorithm in terms of the algorithms and the inputs.

There are 3 types of Asymptotic notations:

1. Big-O notation: It describes the worst-case running time of an algorithm. To calculate this we count the number of operations it will take in the worst-case scenario with the input 'n'.
2. Big Omega() notation: It describes the best running time of an algorithm. To calculate this we count the number of operations it will take in the best-case scenario with the input 'n'.
3. Big Theta() notation: It is used to calculate the average runtime of an algorithm.

Constant time O(1):

for(int i=0;i<10;i++){
    cout<<"Hello world"<<endl;
}

Here this is constant time. There is no variable here. Always we get 10 "Hello world" on the screen.

Linear time O(n):

for(int i=0;i<n;i++){
    cout<<"Hello world"<<endl;
}

Here this is linear time. There is a variable called n. Always we get (n) number of "Hello world" on the screen.

Quadratic time O(n2):

for(int i=0;i<n;i++){
     for(int j=0;j<n;j++){  
        // do something
     }
}

Here this is linear time. There is a variable called n. Always we get (n) number of "Hello world" on the screen.

Cubic time O(n2):

for(int i=0;i<n;i++){
     for(int j=0;j<n;j++){  
        for(int k=0;k<n;k++){
           // do something
        }   
     }
}

Here this is linear time. There is a variable called n. Always we get (n) number of "Hello world" on the screen.