// Contoh Bab 10: mencacah berapa kali bagian terdalam dijalankan.
//
// Compile:  g++ -std=c++17 -O2 -o langkah exercises/10/03-hitung-langkah.cpp
// Jalankan: ./langkah
// Coba n = 1000 lalu n = 2000 dan bandingkan angkanya.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long linear = 0;
    for (int i = 0; i < n; i++) linear++;

    long long kuadratik = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            kuadratik++;

    long long segitiga = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            segitiga++;

    long long logaritmik = 0;
    for (int i = 1; i <= n; i *= 2) logaritmik++;

    cout << "O(n)      : " << linear << "\n";
    cout << "O(n^2)    : " << kuadratik << "\n";
    cout << "O(n^2 / 2): " << segitiga << "\n";
    cout << "O(log n)  : " << logaritmik << "\n";
    return 0;
}