Lecture 02 - Time Complexity

Notation

1. Best case → Omega Notation - Ω

   Describes the minimum time the algorithm could take.

   example: Linear Search - Ω(1)

2. Average case → Theta Notation - Θ

   Describes the tight bound - when best and worst cases grow the same.

   • Traversing an array → Θ(n)

3. Worst case → Big O Notation - O

   Describes the maximum time an algorithm can take.( most commonly used )

   Binary Search → O(log n)

Ω <= Θ <= O

Types

1. constant time O(1)

    #include <iostream>
    using namespace std;
    int main() {
        int x = 10;
        int y;
        cin >> y;
        int z = x + y;     // operation take constant time => O(1)
        cout << z << endl; 
        return 0;
    }
    // Total operations: Constant (independent of input)
   

2. Linear time O(n)

    #include <iostream>
    using namespace std;
    int main() {
        int a = 5;                 // O(1)
        int n;
        cin>>n;
        for(int i=0 ; i<n ; i++){  // loop runs n times
            a+=1; //O(1)
        }
        cout<< a << endl;
        return 0;
    }
   

3. Quadratic time O(n²)

    #include <iostream>
    using namespace std;
    int main() {
        int a = 5;
        int n;
        cin>>n;
        for(int i=0 ; i<n ; i++){        // Outer loop: O(n)
            for (int j = 0; j < n; j++)  // Inner loop: O(n)
            {
                cout<<"*"<<" "; //O(1)
            }
            cout<<endl;        
        }
        return 0;
    }
   

    #include <iostream>
    using namespace std;
    int main() {
        int a = 0, b = 5, c = 10, n;
        cin>>n; 
        a = b + c / 2 + n;  // O(1)
   
        for (int i = 0; i < n / 3; i++) {      // Outer loop: O(n/3) ≈ O(n)
            for (int j = 1; j < n; j += 2) {   // Inner loop: O(n/2) ≈ O(n)
                a++; // O(1)
            }
        }
   
        cout << "Final value of a: " << a << endl;
        return 0;
    }
   

4. Cubic time O(n³)

    #include <iostream>
    using namespace std;
    int main() {
        int x, y, z, n, a;
        cin >> x;
        cin >> y;
        z = x + y; // O(1)
        cin >> n;
        for (int i = 0; i < n ; i++) {          // Outer loop: O(n)
            for (int j = 1; j < n; j++) {       // Middle loop: O(n)
                for (int k = 0; k < n; k++) {   // Inner loop: O(n)
                    a+=1;  //O(1)
                }
            }
        }
        cout << "Final value of a: " << a << endl;
        return 0;
    }
   

5. Logarithmic time O(log n)

    #include <iostream>
    using namespace std;
    int main() {
        int n, a;
        cin >> n;
        for (int i = 0; i < n ; i*=2 ) {  // O(log n)
            a++;
        }
        cout << "Final value of a: " << a << endl;
        return 0;
    }
   

• This above code will run for i = 1, 2, 4, 8, 16, 32, … , 2^k-1 → as soon as 2^k is greater than or equal to n it breaks

  It breaks for 2^k = n → taking log₂() both side

  k = log₂n ≈ O(log n)

6. Linear logarithmic time O(n logn)

    #include <iostream>
    using namespace std;
    int main()
    {
        int a = 10, n;
        cin >> n;
        for (int i = 0; i < n; i = i + 2)       // Outer loop: O(n/2) ≈ O(n)
        {
            for (int j = 1; j < n; j = j * 2)   // Outer loop: O(log₂n) ≈ O(log n)
            {
                a++; // O(1)
            }
        }
        cout << a;
        return 0;
    }                                            // total : O(n * log n)
   

   Learning best and worst case scenario through code

    #include <iostream>
    using namespace std;
   
    int main() {
        int a, b, c = 0, n, m;
        cin >> a >> n >> m;
        b = n;
        if (a > 0) {
            for (int i = 0; i < n; i++) {
                b++;
            }
            // Time complexity: O(n)
        } else {
            while (b != 0) {
                b--;
                for (int j = 0; j < m; j++){
                    c++;
                }
            }
            // Time complexity: O(n * m) ≈ O(n²)
        }
        // Best case : Ω(n)
        // worst case : O(n²)
        return 0;
    }