Определение большого времени выполнения этих различных циклов?

У меня есть ряд вопросов, на которые мне нужны отзывы и ответы. Я прокомментирую, что я думаю, что это не домашнее задание, а скорее подготовкак экзамену.

Моя основная проблема заключается в определении количества итераций цикла для различных случаев. Как бы попытаться это выяснить?

Оцените время работы.

В2.

 for(int i =0 ; i < =n ; i++) // runs n times
   for(int j =1; j<= i * i; j++) // same reasoning as 1. n^2
      if (j % i == 0)
         for(int k = 0; k

Правильный ответ: N × N2 × N = O(N^4)

На следующие вопросы ниже у меня нет правильных ответов.

В3.a)

     int x=0; //constant
     for(int i=4*n; i>=1; i--) //runs n times, disregard the constant
         x=x+2*i;

Мой ответ: O(n)

b) Предположим для простоты, что n = 3^k

    int z=0;
    int x=0;
    for (int i=1; i<=n; i=i*3){ // runs n/3 times? how does it effect final answer?
       z = z+5;
       z++;
       x = 2*x;
    }

Мой ответ: O(n)

c) Предположим для простоты, что n = k^2 ,

   int y=0; 
   for(int j=1; j*j<=n; j++) //runs O(logn)?  j <= (n)^1/2
   y++; //constant

Мой ответ: O(logn)

d)

  int b=0; //constant
  for(int i=n; i>0; i--) //n times
    for(int j=0; j

Мой ответ: O(n^3)

(e)

 int y=1;
 int j=0;
 for(j=1; j<=2n; j=j+2) //runs n times
    y=y+i;
 int s=0;
 for(i=1; i<=j; i++) // runs n times
 s++;

Мой ответ: O(n)

(f)

 int b=0;
 for(int i=0; i

Мой ответ: O(n^4)

(g) Предположим для простоты, что n = 3k для некоторого положительного целого числа k.

   int x=0;
   for(int i=1; i<=n; i=i*3){  //runs 1, 3, 9, 27...for values of i. 
     if(i%2 != 0) //will always be true for values above
      for(int j=0; j

Мой ответ: O (n x log основание 3 n? )

(h) Предположим для простоты, что n = k2 для некоторого положительного целого числа k.

   int t=0;
   for(int i=1; i<=n; i++) //runs n times
      for(int j=0; j*j<4*n; j++) //runs O(logn)
         for(int k=1; k*k<=9*n; k++) //runs O(logn)
            t++;

Мой ответ: n x logn x log n = O(n log n^2)

(i) Предположим для простоты, что n = 2s для некоторого положительного целого числа s.

   int a = 0;
   int k = n*n;
     while(k > 1) //runs n^2
     {
       for (int j=0; j

Мой ответ: O(n^4)

(j)

  int i=0, j=0, y=0, s=0;
  for(j=0; j

Мой ответ: O(n^3)

(k) интервал i=1, z=0; while( z

Мой ответ: O(n)

(m) Предположим для простоты, что n = 2s для некоторого положительного целого числа s.

  int a = 0;
  int k = n*n*n;
  while(k > 1) //runs O(logn) complexity
   {
     for (int j=0; j

Мой ответ: O(n^3 log n)

Вопрос 4

http://i.stack.imgur.com/zMkt7.jpg

• a) Верно, так как оно ограничено снизу числом n ^2
• b) Ложь - f(n) не строго меньше, чем g(n)
• c) Верно
• d) Верно -ограничено n^10
• e) Ложно - f(n) не строго меньше, чем g(n)
• f) Верно
• g) Верно
• h) неверно - поскольку не равно O(nlogn)
• i) верно
• j) не уверен
• л) не уверен
• л) не уверен - как мне вообще попытаться это сделать?*

Заранее спасибо.