مجموعة تمارين متنوعة على التعقيد في الخوارزميات complexity exercises in algorithms

مجموعة تمارين متنوعة على التعقيد في الخوارزميات complexity exercises in algorithms

big O

what is the complixity of the following algorithm:

for (int i = 0; i < n; i++)

sum = sum - i;

---------------------------------------------------------------

answer: O(n)

what is the complixity of the following algorithm:

for (int i = 0; i < n * n; i++)

sum = sum + i;

---------------------------------------------------------------

answer: O(n^2)

what is the complixity of the following algorithm:

i=1;

while (i < n) {

sum= sum + i;

 i = i*2

}

---------------------------------------------------------------

answer: O(log n)

what is the complixity of the following algorithm:

for (int i = k; i < n; i = i * m)

{

statement1;

statement2;

}

---------------------------------------------------------------

answer: O(Logm (n - k) )

what is the complixity of the following algorithm:

for (int i = k; i <= n; i = i * m)

{

statement1;

statement2;

}

---------------------------------------------------------------

answer: O(Logm (n - k) + 1)

what is the complixity of the following algorithm:

sum = 0

for(int i = 0; i < n; i++)

for(int j = 0; j < n; j++)

sum += i * j ;

---------------------------------------------------------------

answer: O(n^2)

what is the complixity of the following algorithm:

i = 1;

while(i <= n) {

j = 1;

while(j <= n){

statements of constant complexity;

j = j*2;

}

i = i+1;

}

---------------------------------------------------------------

answer: O(n log n)

what is the complixity of the following algorithm:

for(int i = 1; i <= n; i++)

for(int j = 1; j <= m; j++)

sum = sum + i + j;

---------------------------------------------------------------

answer: 3mn = O(mn)

what is the complixity of the following algorithm:

for(int i = 1; i <= n; i++)

for(int j = 1; j <= m; j++)

for(int k = 1; k <= p; k++)

sum = sum + i + j + k;

---------------------------------------------------------------

answer: 4pmn = O(pmn)

what is the complixity of the following algorithm:

for (int j = 0; j < n * n; j++)

sum = sum + j;

for (int k = 0; k < n; k++)

sum = sum - l;

System.out.print("sum is now ” + sum);

---------------------------------------------------------------

answer: O(n^2)

what is the complixity of the following algorithm:

for (i = 1; i <= n; i++)

sum = sum + i;

---------------------------------------------------------------

answer: O(n)

what is the complixity of the following algorithm:

for (i = 1; i <= n; i++) {

for (j = 1; j <= n; j++)

sum = sum + i + j;

}

---------------------------------------------------------------

answer: O(n^2)

what is the complixity of the following algorithm:

for (i = 1; i <= n; i++)

sum = sum + i;

---------------------------------------------------------------

answer: O(n)

what is the complixity of the following algorithm:

for (j = 1; j <= n; j++)

sum = sum + j * j;

---------------------------------------------------------------

answer: O(n)

what is the complixity of the following algorithm:

 if (test == 1)

---------------------------------------------------------------

answer:O(1)

what is the complixity of the following algorithm:

for (i = 1; i <= n; i++)

sum = sum + i;

---------------------------------------------------------------

answer: O(n)

what is the complixity of the following algorithm:

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++)

sum = sum + i + j;

---------------------------------------------------------------

answer: O(n^2)

what is the complixity of the following algorithm:

for(i = 1; i <= n; i++)

for(j = 1; j <= n; j++)

for(k = 1; k <= n; k++)

sum = sum + i + j + k;

if (test == 1)

for (i = 1; i <= n; i++)

for(j = 1; j <= n; j++) sum =

sum + i;

else for (i = 1; i <= n;

i++)

sum = sum + i + j;

---------------------------------------------------------------

answer: O(n^3(

what is the complixity of the following algorithm:

for(int i = 0; i < X.length; i++)

sum += X[i];

---------------------------------------------------------------

answer: o(n)

what is the complixity of the following algorithm:

for(int i = 0; i < Y.length; j++)

for(int j = 0; j < Y[0].length; j++)

sum += Y[i][j];

---------------------------------------------------------------

answer: o(n2)