// Tres funciones que no hacen nada útil: solo suman 1 por cada unidad de trabajo, para comparar
// lo que cuestan con la recurrencia que se lee en su código.
#pragma once

// T(n) = 2 T(n/2) + n
inline void two_calls_linear(int n, long long& work) {
    if (n <= 1) {
        work++;
        return;
    }
    for (int i = 0; i < n; i++) {
        work++;
    }
    two_calls_linear(n / 2, work);
    two_calls_linear(n / 2, work);
}

// T(n) = 3 T(n/2) + n
inline void three_calls_linear(int n, long long& work) {
    if (n <= 1) {
        work++;
        return;
    }
    for (int call = 0; call < 3; call++) {
        three_calls_linear(n / 2, work);
    }
    for (int i = 0; i < n; i++) {
        work++;
    }
}

// T(n) = 8 T(n/2) + n²
inline void eight_calls_quadratic(int n, long long& work) {
    if (n <= 1) {
        work++;
        return;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            work++;
        }
    }
    for (int call = 0; call < 8; call++) {
        eight_calls_quadratic(n / 2, work);
    }
}