Algorithms MCQ Questions and Answers - Fundamentals - Part 1

Algorithms MCQ – Data Structures & Complexity – Part 3

Computer architecture MCQ questions and answers for the preparation of tests, exams, and certifications. So you will find questions about loops and conditionals, data structure, complexity, flowchart, pseudocode, and much more. This systematic learning method will easily prepare anyone to pass their exam.

1. Which of the following cases does not exist in the complexity theory?

A Best case

B Worst case

C Average case

D Null case

2. What is the worst case time complexity of insertion sort where the position of the data to be inserted is calculated using a binary search?

A N

B N * logN

C N ^ 2

D N (logN) ^ 2

The application of binary search to calculate the position of the data to be inserted does not reduce the time complexity of the insertion sort. Indeed, inserting data at an appropriate position involves two steps:

Calculate the position.
Move the data from the calculated position in step 1 one step to the right to create a space where the data will be inserted.

Using binary search reduces the time complexity of step 1 from O(N) to O(logN). However, the time complexity of step 2 still remains O(N). The overall complexity therefore remains O(N ^ 2).

3. What is the time complexity of the function below?

void algo(int n, int arr[])
{
    int i = 0, j = 0;
    for(; i < n; ++i)
        while(j < n && arr[i] < arr[j])
            j++;
}

A O(n)

B O(n^2)

C O(n * logn)

D O(n(logn)^2)

The time complexity seems to be O(n ^ 2) because of two loops. But note that the variable j is not initialized for each value of the variable i. Thus, the inner loop executes at most n times. Please take note of the difference between the given function and the function below:

void algo2(int n, int arr[]) {
     int i = 0, j = 0;
     for(; i < n; ++i) {
          j = 0; 
          while(j < n && arr[i] < arr[j]) 
               j++; 
     } 
}

4. The worst case occurs in the linear search algorithm when ________?

A The element is in the middle of the array

B The element is not in the array

C The element is in the last position of the array

D The element is in the last position of the array or it does not exist

5. Consider the following for loops:

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

B for(i = 0; i < n; i += 2)

C for(i = 1; i < n; i *= 2)

D for(i = n; i < -1; i /= 2)

If n is the size of the input, which loop is more efficient?

The time complexity of the first for loop is O(n).
The time complexity of the second loop is O(n / 2), which is equivalent to O(n) in asymptotic analysis.
The time complexity of the third for loop is O(logn).
The fourth loop does not end.

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

A X will be a better choice for all inputs

B X will be a better choice for all except small entries

C X will be a better choice for all except large entries

D Y will be a better choice for small entries

In the asymptotic analysis, we consider the growth of the algorithm in terms of the input size. An algorithm X is said to be asymptotically better than Y if X takes less time than y for all input sizes.

7. The complexity of the bubble sorting algorithm is _____?

A O(n)

B O(log n)

C O(n2)

D O(n * log n)

8. What is the time complexity of the Floyd-Warshall algorithm to calculate all the shortest paths of a pair in an n-vertex graph?

A O(n ^ 2logn)

B Θ(n ^ 2logn)

C Θ(n ^ 4)

D Θ(n ^ 3)

The Floyd – Warshall algorithm uses three nested loops to calculate all the shortest paths. Therefore, the time complexity is Θ(n ^ 3).

9. Is the statement log(n!) = Θ(n log n) valid?

A True

B False

Order of growth of (log n!) and (n log n) is identical for large values of n, i.e., Θ(log n!) = Θ(n log n). The expression Θ(log n!) = Θ(n log n) can easily be deduced from the approximation of log n! = n log n - n + O (log (n))

10. Arrays are the best data structures

A For relatively permanent data collections

B For data collections whose structure is constantly changing

C All the answers are true

D None of the above