#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# %%
n = 1000

# %% A
x = 0
for i in range(4 * n, 0, -1):
    x = x + 2 * i

# 4n -> O(n)

# %% B
z = 0
x = 0
i = 1
while i <= n:
    z += 5
    x *= 2
    i *= 3

# O(ln(n))

# %% C
y = 0
j = 1
while j*j <= n:
    y += 1
    j += 1

# O(sqrt(n))

# %% D
b = 0
i = n
for i in range(n, 0, -1):
    for j in range(0, i, 1):
        b += 5

# n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 -> O(n^2)

# %% E
y = 0
for j in range(0, 2*n + 1, 2):
    y += j

s = 0
for i in range(1, j + 1, 1):
    s += 1

# n + 2n = 3n -> O(n)

# %% F
b = 0
for i in range(1, n+1, 1):
    for j in range(1, (i*n)+1, 1):
        b += 5

# n + 2n + 3n + ... +nn = n * n(n+1)/2 -> O(n^3)

# %% G
x = 0
i = 1
while i <= n:
    if i % 2 != 0:
        for j in range(0, i, 1):
            x += 1
    i *= 3

# O(n) because 1 + 3 + 9 + 27 + ... + 3^(ln(n)) is geometric sum with
# a=1 and r=3, therefore (3^(ln(n) + 1) - 1)/(3 - 1) = (3n - 1)/2 -> O(n)

# %% H
t = 0
for i in range(1, n+1, 1):
    j = 0
    while j*j < 4*n:
        k = 1
        while k*k <= 9*n:
            t += 1
            k += 1
        j += 1

# n * sqrt(n) * sqrt(n) -> O(sqrt(n))

# %% I
a = 0
k = n*n
while k > 1:
    for j in range(0, n*n, 1):
        a += 1
    k /= 2

# outer: log(n^2) = 2*log(n)
# inner: n^2
# O(n2 log n)

# %% J
i = 0
j = 0
y = 0
s = 0
for j in range(1, n+1, 1):
    y += j
    for i in range(1, y+1, 1):
        s += 1

# 1 + 3 + 6 + 10 + ... = sum of i=1 to n: i(i+1)/2
# = 1/2 * (sum of i=1 to n: i^2 + sum of i=1 to n: i)
# = 1/2 * (n(n+1)(2n+1)/6 + n(n+1)/2)
# -> n^3

# %% K
i = 1
z = 0
while z < n*(n+1)/2:
    z += i
    i += 1

# O(n)

# %% L
a = 0
k = n*n*n
while k > 1:
    for j in range(0, k, 1):
        a -= 1
    k /= 2

# O(n3)
# n^3 + n^3/2 + n^3/4 + n^3/8 = n^3 * 2 = O(n^3)

# %% M
for i in range(0, n, 1):
    j = 0
    while j < n:
        x += 1
        j += i

# infinite
# after correction O(n lg n)
# integration of harmonic series

# %% kmp preparation
m = n // 20
A = "A"*n
B = "A"*m + "$"
kmp = [0] + list(range(m))  # kmp[0] = 0, kmp[i] < i

# %% N
cur = 0
for i in range(n):
    while cur != 0 and A[i] != B[cur]:
        cur = kmp[cur]
    if A[i] == B[cur]:
        cur += 1

# O(n) - follow i-cur and i
# both can only increase, so at worst 2n -> O(n)

# %%
# zoradte funkcie
# 47n^3, 42n, 23n^2 + 4n + 3, 0.0001n^2, 2^n, 3^n, n^200*1.99^n, n^n,
# 2^(ln n), n!, ln n, ln n^100, ln n!, ln n^n, n ln n, n (ln n)^2, (n+1)!