Визначення складності.
1.

func f(int n):
    int count := 0
    for i := 0 to n:
        for j:= 0 to i:
            count++;
    print (count)

Моя версія:   O(n*n!)

2.

func f(int n):
    int count := 0
    for i := 0 to n:
        for j:=i+1 to n:
            for k:=i to j:
                count++;
    print (count)

Моя версія:   O(n*n!*log(n))

2.

func f(int n):
    int count := 0
    int m := n
    while n > 0:
        for i := 0 to n:
            count++;
        n /= 2
    print (count)

Моя версія:   O(n*something_responsible_for_while_loop) Але тут не знаю. Думав так: внутрішній цикл: зрозуміло n. Складності вкладених циклів перемножаються, тому це n треба помножити на щось що відповідає за while цикл.

4

func f(int n):
    int count := 0
    for i=0; i<=n; i++:
        for j:=i; j<=n; j+=i:
            count++;
    print (count)

Моя відповідь: O(n * i_dont_know)

От напр. перша функція.

func f(int n):
    int count := 0
    for i := 0 to n:
        for j:= 0 to i:
            count++;
    print (count)

Перший ж цикл виконається n разів, другий i [ (i=0) (i=1) (i=2) (i=3) ... ] Відносно n, i - це n! ні?

Відносно n, i - це n! ні?

3. Внутрішній цикл - O(n), зовнішній виконується log2(n) разів (бо кожного разу увічі менше). Отже, O(n*log(n)).

func f(int n):
    int count := 0
    int m := n
    while n > 0:
        for i := 0 to n:
            count++;
        n /= 2
    print (count)

4. Знову O(n*log(n)).

func f(int n):
    int count := 0
    for i=0; i<=n; i++:
        for j:=i; j<=n; j+=i:
            count++;
    print (count)

koala написав:

4. Знову O(n*log(n)).

Нєа. Давайте ще раз подивимось на код:

Q-bart написав:

func f(int n):
    int count := 0
    for i=0; i<=n; i++:
        for j:=i; j<=n; j+=i:
            count++;
    print (count)

count=0
i=0
j=i        # j == 0
count++    # count == 1
j+=i       # j == 0
j<=n       # true
count++    # count == 2
j+=i       # j == 0
j<=n       # true
...
j<=n       # завжди true для всіх n >= 0

Вічний цикл.