C++: 11 - Сложность вычислений

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