// Cuenta llamadas, trabajo y profundidad de cuatro funciones recursivas.
#include <algorithm>
#include <cstdio>

struct Tally {
    long long calls = 0;
    long long work = 0;
    int deepest = 0;
};

// T(n) = T(n/2) + 1
void one_half(long long n, int depth, Tally& tally) {
    tally.calls++;
    tally.work++;
    tally.deepest = std::max(tally.deepest, depth);
    if (n <= 1) {
        return;
    }
    one_half(n / 2, depth + 1, tally);
}

// T(n) = 2 T(n/2) + 1
void two_halves(long long n, int depth, Tally& tally) {
    tally.calls++;
    tally.work++;
    tally.deepest = std::max(tally.deepest, depth);
    if (n <= 1) {
        return;
    }
    two_halves(n / 2, depth + 1, tally);
    two_halves(n / 2, depth + 1, tally);
}

// T(n) = 2 T(n/2) + n
void two_halves_linear(long long n, int depth, Tally& tally) {
    tally.calls++;
    tally.work += n;
    tally.deepest = std::max(tally.deepest, depth);
    if (n <= 1) {
        return;
    }
    two_halves_linear(n / 2, depth + 1, tally);
    two_halves_linear(n / 2, depth + 1, tally);
}

// T(n) = 2 T(n-1) + 1
void two_minus_one(long long n, int depth, Tally& tally) {
    tally.calls++;
    tally.work++;
    tally.deepest = std::max(tally.deepest, depth);
    if (n == 0) {
        return;
    }
    two_minus_one(n - 1, depth + 1, tally);
    two_minus_one(n - 1, depth + 1, tally);
}

using Recursive = void (*)(long long, int, Tally&);

void print_table(const char* title, Recursive fn, const long long* sizes, int count) {
    std::printf("%s\n", title);
    std::printf("%10s %12s %12s %8s\n", "n", "llamadas", "trabajo", "profund.");
    for (int i = 0; i < count; i++) {
        Tally tally;
        fn(sizes[i], 0, tally);
        std::printf("%10lld %12lld %12lld %8d\n", sizes[i], tally.calls, tally.work, tally.deepest);
    }
    std::printf("\n");
}

int main() {
    const long long powers[] = {8, 16, 1024, 2048};
    const long long others[] = {5, 6, 7, 9, 1000, 1500};
    const long long small[] = {5, 10, 20};

    print_table("T(n) = T(n/2) + 1", one_half, powers, 4);
    print_table("T(n) = 2 T(n/2) + 1", two_halves, powers, 4);
    print_table("T(n) = 2 T(n/2) + 1, n que no es potencia de 2", two_halves, others, 6);
    print_table("T(n) = 2 T(n/2) + n", two_halves_linear, powers, 4);
    print_table("T(n) = 2 T(n-1) + 1", two_minus_one, small, 3);
    return 0;
}