مجموعة تمارين متنوعة على التعقيد في الخوارزميات 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)
