ANALYSIS OF ALGORITHMS

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 complexity of Binary search algorithm is

• O(n)

• O(log n)

• O(n2)

• O(n log n)

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)

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)

A linear function takes the form

• f(n) = an + b

• f(n) = an2 +bn + c

• f(n) = alog2n

• f(n) = a + b

Find the slowest algorithm:

• O (n)

• O (n^2)

• O (n!)

• O (2^n)

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

• Exponential Time

• Linear Time

• Polynomial Time

• Constant Time

What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

• X will be a better choice for all inputs

• X will be a better choice for all inputs except possibly small inputs

• X will be a better choice for all inputs except possibly large inputs

• Y will be a better choice for small inputs

Consider this list of numbers: 3 4 6 7 8 9. If the number 9 was to be found using a linear search, how many comparisons need to be made?

• 6
• 3
• 8
• 4

What is the main disadvantage of a binary search compared to a linear search?

• It requires the data to be in order
• It requires more memory
• It does not execute as quickly with larger data sets
• Not all CPUs are capable of executing the algorithm