Theory quiz

What is the time complexity of the quicksort algorithm in the average case?

• A. O(n)

• B. O(n log n)

• C. O(n^2)

• D. O(log n)

merge sort is a ......................

• searching technique

• in-place sorting technique

• not in place sorting technique

• stable sorting method

For merging two sorted lists of sizes m and n into a sorted list of size m+n, we require comparisons of

• 1. O(m)

• 1. O(n)

• 1. O(m+n)

• 1. O(logm + logn)

To main measures of the efficiency of an algorithm are?

• space and data

• data & time

• time & capacity

• time &space

Which of the following is a Divide and Conquer algorithm?

• bubble sort

• merge sort

• quick sort

• insertion sort

What is the technique called in which it does not require extra memory for carrying out the sorting procedure?

• in-place

• stable

• in-partition

• unstable

Which of the following is incorrect? Algorithms can be represented:

• as programs

• as pseudo-codes

• as syntax

• as flow chart

What should be considered when designing an algorithm?

• if this software is used correctly

• if this hardware is used correctly

• if there is more than one way to solve the problem

• all of the above

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)

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

• 3

• 4

• 6

• 9