Algorithm Analysis

What is the time complexity of following code:

int i, j, k = 0;

for (i = n / 2; i <= n; i++) {

for (j = 2; j <= n; j = j * 2) {

k = k + n / 2;

}

}

• O(n)

• O(nLogn)

• O(n^2)

• O(n^2Logn)

What is the time complexity of following code:

int a = 0;

for (i = 0; i < N; i++) {

for (j = N; j > i; j--) {

a = a + i + j;

}

}

• O(N)

• O(N*log(N))

• O(N * Sqrt(N))

• O(N*N)

The complexity of Binary search algorithm is

• O(n)

• O(log n)

• O(n2)

• O(n log n)

What is the time complexity of this code

int a = 0, i = N;

while (i > 0)

{

a += i;

i /= 2;

}

• O(N)

• O(Sqrt(N))

• O(N / 2)

• O(log N)

The number of executions grows extremely quickly as the size of the input increases

• Exponential Time

• Linear Time

• Polynomial Time

• Constant Time

Which of the following has the highest time efficiency (consumes less time) in asymptotic efficiency class?

• n

• log n

• n log n

Factors that affect an Algorithm Runtime

• Computer performance

• Complexity

• Input Size

• All the factors listed.

Which is the worst case of a linear search?

• Probability of the first match occurring in the ith position of the list is p/n for every i, and the no. of comparisons made by the algorithm in such situation is obviously i.

• The first element in the list is equal to the search key.

• There are no matching elements or the matching element happens to be the last one in the list.

• None of the above.

Asymptotic Complexity is

• approaching a given value as an expression containing a variable tends to infinity.

• highest order term is more important.

• describing the growth rate of the time or space complexity with respect to input size

Which is True about Big-Oh?

• Notation is used when an algorithm is bounded both above and below by the same kind of function.

• Notation provides an upper bound for the growth rate of the given function.

• Notation provides a lower bound.

• t(n) ≥ cg(n)