TDS Lec 7&8

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 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

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

Consider this list of numbers L: 3 4 5 6 7 8 9. Which number would be checked first in a binary search?

• 6
• 3
• 9
• 4

What is meant by the time complexity of an algorithm?

• The amount of time required to solve a particular problem
• How difficult a problem is to solve
• How many lines of code are required to solve a problem
• How quickly a solution can be developed

What two pieces of information allow you to analyse an algorithm?

• Time Complexity
• Space Complexity
• Size Complexity
• Complex Complexity
• Simplicity Complex

If for an algorithm time complexity is given by O(1) then complexityof it is:

• constant

• polynomial

• exponential

• none of the mentioned

If for an algorithm time complexity is given by O(n) then complexityof it is:

• A. constant

• B. linear

• C. exponential

• D. none of the mentioned

Which of the following is the best description of the linear search algorithm?

• Put the elements in order, then go through them one by one until target is found or the end of the list is reached.
• Put the elements in order, compare with the middle value, if not the target: continue to the left or right of the middle and repeat. 
• Elements do not need to be in order. Go through them one by one until target is found or the end of the list is reached.
• Elements do not need to be in order, compare with the middle value, if not the target: continue to the left or right of the middle and repeat.