Data structures & algorithms

#include <print>

int main() {
    const int n = 1000;
    long long a = 0, b = 0, c = 0, d = 0;

    for (int i = 0; i < n; ++i)              // n
        for (int j = 0; j < n; ++j) ++a;     //   × n          = n²

    for (int i = 0; i < n; ++i)              // inner runs i times:
        for (int j = 0; j < i; ++j) ++b;     // 0 + 1 + … + (n-1) = n(n-1)/2  → still Θ(n²)

    for (int i = n; i > 0; i /= 2) ++c;      // halving: ⌊log₂ n⌋ + 1 iterations → Θ(log n)

    for (int i = 1; i <= n; ++i)             // inner runs n/i times:
        for (int j = i; j <= n; j += i) ++d; // n(1 + 1/2 + … + 1/n) ≈ n ln n → Θ(n log n)

    std::println("n²={} triangle={} halving={} harmonic={}", a, b, c, d);
}