Паскаль: 11 - Сложность вычислений

1. Задан массив X[1..N]. Определите число операций сложения, которые выполняются при работе этой программы:
  S:=X[1]+X[N];
for k:=1 to N do
X[k]:=X[k]+X[k]+S;
Для обозначения операции умножения используйте символ *.
Ответ: 
2. Задан массив X[1..N]. Определите число операций умножения, которые выполняются при работе этой программы:
  S:=X[1]*X[N];
for k:=1 to N do begin
X[k]:=2*X[k]+S;
for i:=1 to 3 do
S:=S*2;
end;
Для обозначения операции умножения используйте символ *.
Ответ: 
3. Задан массив X[1..N]. Определите число операций сложения, которые выполняются при работе этой программы:
  S:=X[1]+X[N]+3;
for k:=1 to N do
for m:=1 to N do
X[k]:=X[k]+S;
Для обозначения операции умножения используйте символ *.
Ответ: 
4. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  S:=X[1]+X[N];
for k:=1 to N do
for m:=1 to 5 do
X[k]:=X[k]+S;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
5. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  S:=X[1]+X[N];
for k:=1 to N do
for m:=1 to k do
X[k]:=X[k]+X[m]+S;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
6. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  S:=X[1]+X[N];
for k:=1 to N do
for m:=1 to N do
for q:=1 to k do
X[k]:=X[k]+X[q]+S;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
7. Определите наиболее точную оценку временной сложности алгоритма вычисления функции:
  function Rec(N: integer): integer;
begin
Rec:=0;
if N > 3 then
Rec:=Rec+Rec(N-1)+2*Rec(N-2);
end;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
8. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  S:=X[1]+X[N];
for k:=1 to N do
for m:=1 to 2*N*N do
X[k]:=X[k]+m*X[k]+S;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
9. Определите наиболее точную оценку временной сложности алгоритма:
  L:= 1; 
R:= N + 1;
while L < R-1 do begin
c:= L + div(R-L,2)
if R < X[c] then R:=c
else L:=c;
end;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
10. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  k:=0;
for i:=1 to N do
if X[i] = R then begin
k:=i;
break;
end;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
11. Задан массив A[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  for i:=1 to N-1 do
for j:=N-1 downto i do
if A[j]>A[j+1] then begin
temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
end;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)