import math
import csv

def max_n_log(time_seconds):
    # f(n) = log2(n)
    # czyli log2(n) <= microseconds -> n <= 2^microseconds
    microseconds = time_seconds * 1_000_000
    log10_n = microseconds * math.log10(2)   # zeby nie wybuchlo, zapis jako 10^x
    return f"≈ 10^{log10_n:,.0f}".replace(",", " ")


def max_n_linear(time_seconds):
    # f(n) = n, easy, n <= microseconds
    microseconds = time_seconds * 1_000_000
    return f"{int(microseconds):,}".replace(",", " ")


def max_n_nlogn(time_seconds):
    # f(n) = n * log2(n)
    # tego nie rozwiazesz recznie, trzeba przyblizenie
    microseconds = time_seconds * 1_000_000
    left, right = 1, 10**18   # na pewno wystarczy lol
    while left < right:
        mid = (left + right) // 2
        f = mid * math.log2(mid)
        if f <= microseconds:
            left = mid + 1
        else:
            right = mid - 1
    return f"{left:,}".replace(",", " ")


def max_n_quadratic(time_seconds):
    # f(n) = n^2 -> n <= sqrt(microseconds)
    microseconds = time_seconds * 1_000_000
    n = int(math.sqrt(microseconds))
    return f"{n:,}".replace(",", " ")


def max_n_cubic(time_seconds):
    # f(n) = n^3 -> n <= microseconds^(1/3)
    microseconds = time_seconds * 1_000_000
    n = int(round(microseconds ** (1/3)))
    return f"{n:,}".replace(",", " ")


def max_n_exponential(time_seconds):
    # f(n) = 2^n -> 2^n <= microseconds -> n <= log2(microseconds)
    microseconds = time_seconds * 1_000_000
    n = int(math.log2(microseconds))
    return f"{n:,}".replace(",", " ")


def max_n_factorial(time_seconds):
    # f(n) = n! -> n! <= microseconds -> trzeba jechac petla bo inaczej nie policzysz
    microseconds = time_seconds * 1_000_000
    n = 1
    fact = 1
    while fact <= microseconds:
        n += 1
        fact *= n
    return f"{n-1:,}".replace(",", " ")


# dobra tu ustawiamy czasy
czasy = [
    ("1 sekunda", 1),
    ("1 minuta", 60),
    ("1 godzina", 3600),
    ("1 dzień", 86400),
    ("1 miesiąc", 30 * 86400),
    ("1 rok", 365 * 86400)
]


# export to csv using primewriter
with open("czasy_transposed.csv", "w", newline="", encoding="utf-8") as f:
    writer = csv.writer(f)

    # kolumny: nagłówek z etykietami czasu
    header = ["label"] + [label for label, _ in czasy]
    writer.writerow(header)

    # helper do pisania wiersza
    def write_row(name, func):
        row = [name] + [func(seconds) for _, seconds in czasy]
        writer.writerow(row)

    # teraz każdy wiersz odpowiada jednej funkcji złożoności
    writer.writerow(["seconds"] + [seconds for _, seconds in czasy])
    write_row("lg(n)", max_n_log)
    write_row("n", max_n_linear)
    write_row("n·lg(n)", max_n_nlogn)
    write_row("n²", max_n_quadratic)
    write_row("n³", max_n_cubic)
    write_row("2ⁿ", max_n_exponential)
    write_row("n!", max_n_factorial)

# i lecimy z tabela
for label, seconds in czasy:
    print("================================")
    print(f"{label.upper()}")   # no ładnie niech wygląda
    print("================================")
    print(f"lg(n):       n ≤ {max_n_log(seconds)}")
    print(f"n:           n ≤ {max_n_linear(seconds)}")
    print(f"n·lg(n):     n ≤ {max_n_nlogn(seconds)}")
    print(f"n²:          n ≤ {max_n_quadratic(seconds)}")
    print(f"n³:          n ≤ {max_n_cubic(seconds)}")
    print(f"2ⁿ:          n ≤ {max_n_exponential(seconds)}")
    print(f"n!:          n ≤ {max_n_factorial(seconds)}")
    print()  # pusta linia zeby nie bolało w oczy

# porownaj na wykresie zlozonosci dla osi n / czas
import matplotlib.pyplot as plt
import numpy as np

# dobra, tu robimy dane testowe, bo tych ogromnych liczb i tak nie narysujesz sensownie
# weźmy np. n od 1 do 100 (dla 2^n i n!) i do 1e6 (dla n, n^2, n log n)
n_linear = np.linspace(1, 1e6, 500)   # 500 punktow, wystarczy
n_small = np.arange(1, 30)             # do wykładniczych

# przeliczamy "czas" w mikrosekundach (nie ma znaczenia jednostka, chodzi o kształt)
y_log = np.log2(n_linear)
y_n = n_linear
y_nlogn = n_linear * np.log2(n_linear)
y_n2 = n_linear**2
y_n3 = n_linear**3
y_2n = 2**n_small
y_fact = [math.factorial(i) for i in n_small]

plt.figure(figsize=(10,6))

# rysujemy wykresy — używamy skali log bo inaczej wszystko zniknie xd
plt.plot(n_linear, y_log, label='lg(n)')
plt.plot(n_linear, y_n, label='n')
plt.plot(n_linear, y_nlogn, label='n·lg(n)')
plt.plot(n_linear, y_n2, label='n²')
plt.plot(n_linear, y_n3, label='n³')
plt.plot(n_small, y_2n, label='2ⁿ')
plt.plot(n_small, y_fact, label='n!')

plt.yscale("log")
plt.xscale("log")

plt.title("Porównanie złożoności czasowych algorytmów")
plt.xlabel("Rozmiar problemu n (skala log)")
plt.ylabel("Czas wykonania f(n) (skala log)")
plt.legend()
plt.grid(True, which="both", linestyle="--", alpha=0.4)

# troche marginesu bo n! szybko idzie w kosmos
plt.tight_layout()
plt.show()