Оценки сложности алгоритмов

[ConstantinPerm]

1. Определите порядок сложности алгоритма, задаваемого нижеописанной процедурой. (2 балла)

Procedure st(x,V: integer; var rez:integer);
Var k,m,a:Integer;
Begin
  Rez:=x;
  K:=2;
  repeat
     M:=0;
     a:=1;
     While m<V do
        Begin
           For j:=2 to v-1 do 
             rez:=rez+a*j;
           m:=m + 5
        end; 
     k:=k*k;
   until k>V;
   Rez:=rez*4+1;
End;

2. Постройте функцию сложности рекурсивной процедуры в зависимости от параметра Y, характеризующего сложность входных данных. При построении рекуррентных уравнений запишите их сначала в общем виде и выпишите отдельно значение каждого из слагаемых (Th,TC,TS,Tf). Найдите решение построенных рекуррентных уравнений, определив тем самым аналитический вид функции сложности. Запишите формулу для значения а, которое вычисляет данная процедура. (4 балла)

 Procedure Rec(n:Byte; var a:Real);
       Begin
         If n=0 then a:=1
          Else begin a:=a*2-1; Rec(n-1,a); a:=a+1 end;
         a:=a-1;      
       end;

3. Постройте функцию сложности рекурсивной процедуры в зависимости от параметра a, характеризующего сложность входных данных, при условии, что сложность вызова функции P(x) и равна h. Постройте дерево рекурсивных вызовов процедуры Primer, если первоначальный вызов был Primer(6).. Составьте рекуррентные уравнения и найдите их решение. (4 балла)

 Procedure Primer(a:integer);
     Begin
        If a=3 then begin a:=a*2; P(a) end
         Else
           Begin
             Primer(a-1);
             P(a);
             Primer(a-1);
           End;
     End;

[Abstraction]

0) Обрамляйте код тегом CODE, пожалуйста.
1) Выделите три вложенных друг в друга цикла. Обратите внимание, что в каждом цикле условие выхода меняется лишь один раз за итерацию (скажем, во внешнем цикле k = k*k, пока k не станет больше V, что даёт количество итераций - log2(V)/2), причём условия выхода независимы.
2) Выполните вручную вычисления при n=0, 1, 2. Сразу определите формулу для a. Что обозначается четвёркой "слагаемых" в условии - в лучшем случае подозреваю, но выписывание, к примеру, временной сложности не должно быть проблемой (T(0) = 4, T(n+1) = T(n)+8; если замкнутая форма T(n) не очевидна, можно выписать вручную значения при n=1, 2, 3).
3) Обратить внимание, что первое условие может быть сокращено и a удалено из его тела. Записать рекуррентную формулу (должно получиться T(3)=h+3, T(n+1)=2*T(n)+h+1 или вроде того, в зависимости от соглашений о сложности присваивания и вызовов; замкнутая форма должна включать экспоненту).

[ConstantinPerm]

Сообщение от Abstraction

.
1) Выделите три вложенных друг в друга цикла. Обратите внимание, что в каждом цикле условие выхода меняется лишь один раз за итерацию (скажем, во внешнем цикле k = k*k, пока k не станет больше V, что даёт количество итераций - log2(V)/2), причём условия выхода независимы.

т.е. в первом порядок будет o(log(V)/2)? я пытался выписать поочередно, у меня получилось T=2+o(log(V)(2+o(log(log(V))(o(V)*3 +2)+3

[Abstraction]

Если есть два вложенных друг в друга цикла; внешний исполняется O(f) раз, вложенный - независимо! - O(g) раз, а тело вложенного цикла выполняется за O(1), то вся конструкция выполнится за O(f*g). Всякие константы при этом можно выкинуть, если нас интересует только порядок.
Теперь три вопроса - за сколько исполняются циклы, если Action имеет сложность O(1)?

  K:=2;
  repeat
     Action;
     k:=k*k;
   until k>V;

     M:=0;
     While m<V do
        Begin
           Action;
           m:=m + 5
        end;

           For j:=2 to v-1 do 
             rez:=rez+a*j;