What is Time Complexity 🤷‍♂️

Time complexity is the way to describe how long our code might take to run as the amount of input increase. It doesn't measure actual time - it just provide the rough idea of how the performance growth.

• Best Case → Ω (Omega)

• Average Case → Θ (Theta)

• Worst Case → O (Big-Oh)

---

🧠 Common Time Complexities

int main() {      
    int x, y, z;    ------------------> Line 1
    z = x + y;      ------------------> Line 2
    return 0;       ------------------> Line 3
}

• Variables x, y, z declaration takes constant time → let’s say T1.

• The operation z = x + y is a simple arithmetic operation (addition), which also takes constant time → call it T2.

• return 0 is a simple return statement → constant time as well.

• Total Time Complexity = T1 + T2 = Constant Time = 0(1)

int main() {
    int a, b, c, d, n;    -------------------------> 0(1)
    a = b + c;            -------------------------> 0(1)
    cin >> n;             -------------------------> 0(1)
    for(int i=0; i < n; i++) {    -----------------> 0(n)
        a++;                -----------------------> 0(1)
    }
}

• Based on Previous example we can say that

• input a, b, c, d, n taken constant time → T1

• simple operation and assigning process a = b + c take constant time → T2

• print cin » n also take constant time → T3

• for loop that run from 0 —> n by increasing order so the loop run maximum number of n times

• The inner operation of loop a++ take constant time → T4

• Total Time Complexity = T1 + T2 + T3 + n + T4 so the maximum time from this algo is 0(n)

int main() {
    for(int i=0; i < n; i += 2) { ----------> n/2  = n
        for(int j=0; j < n; j++) {    ------> n * n
            cout << "hello"        ---------> n * n
        }
    }
    return 0;
}

🔹Outer loop:

• • Starts from i = 0 and goes to i < n, incrementing by i += 2.

    • So total number of iterations = n / 2 (ignoring floor/ceil for big-O).

    • In Big-O, we drop constants → this is O(n).

🔹 Inner loop:

• For every value of i, the inner loop runs from j = 0 to j < n, incrementing by 1.

• This loop runs n times → O(n).

🔹 Inner operation:

• cout << "hello"; is a constant time operation → O(1).

• Since it's inside the inner loop, it runs n times per outer loop iteration.

int main() {
    for(int i=1; i < n; i *= 2) { ---------> log2n
        cout << "Hello"
    }
    return 0;
}

• Starts from i = 0 and goes to i < n, incrementing by i *= 2.

• so i = 2^k in the k-th iteration.

• Time Complexity is 0(logn)

int main() {
    for(int i=0; i < n; i++) { ----------------> n
        for(int i=1; i < n; i *= 2) { ---------> n * log2n
            cout << "Hello"
        }
    }
    return 0;
}

• Outer loop run n times

• inner loop run 2^k times means log n time

• Total Time Complexity = n * logn = 0(n log n)

Find Complexity in recursion code

Series of Time Complexity

O(1) < O(log n) < O(n) < O(n log n) < O(n^c) < O(cⁿ) < O(n!)