COCAT - DAA

An image processing application begins with two n×n matrices A and B. The first phase of preprocessing the inputs takes O(n²) steps for each of A and B. The second step involves a convolution of A and B to yield a new matrix C in time O(n³). This is followed by an edge detection phase that takes times O(n²) for matrix C. What is the most accurate and concise description of the complexity of the overall algorithm?

• O(n²)

• O(n³)

• O(n²+n³)

• O(n⁵)

We are trying to determine the worst case time complexity of a library function that is provided to us, whose code we cannot read. We test the function by feeding large numbers of random inputs of different sizes. We find that for inputs of size 300 and 3.000, the function always returns well within one second, but for inputs of size 30,000 it sometimes takes about 1 second and for inputs of size 300,000 it sometimes takes 1-2 minutes. What is a reasonable conclusion we can draw about the worst case time complexity of the library function? (You can assume, as usual, that a typical desktop PC performs 10⁹ basic operations per second.)

• O(n log n)

• O(n²)

• O(n³)

• O(n³ log n)

Suppose f(n) is 2n³+4n+5 and g(n) is 7n⁵ + 5n³ + 12. Let h(n) be a third, unknown function. Which of the following is not possible.

• h(n) is O(f(n)) and h(n) is also O(g(n))

• h(n) is O(g(n)) but h(n) is not O(f(n))

• h(n) is O(f(n)) but h(n) is not O(g(n))

• h(n) is not O(f(n)) and h(n) is also not O(g(n))

If T(n) is O(n² √ n) which of the following is false?

• T(n) is O(n² log n)

• T(n) is O(n³)

• T(n) is O(n³ log n)

• A. T(n) is O(n⁴)

How many times is the comparison i >= n performed in the following program?

int i = 200, n = 80;

main(){

while (i >= n){

i = i-2;

n = n+1;

}

}

• 40

• 41

• 42

• 43

Which of the following statements is not true?

• Quicksort and merge sort are both examples of divide and conquer algorithms.

• If we randomly choose a pivot element each time, quicksort will always terminate in time O(n log n).

• For every fixed strategy to choose a pivot for quicksort, we can construct a worst case input that requires time O(n²).

• If we could find the median in time O(n), quicksort would have worst case complexity O(n log n).

In a min-heap, what is the most accurate description of the worst-case complexity of the operation find_max that reports the value of the largest element in the heap, without removing it?

• O(1)

• O(log n)

• O(n)

• O(n log n)

Consider an alternative to binary search called ternary search that divides the input array into three equal parts and recursively searches one of these three segments. What can we say about the asymptotic worst case complexity of ternary search versus binary search?

• The complexity of ternary search is the same as that of binary search.

• The complexity of binary search is strictly better than that of ternary search.

• The complexity of ternary search is strictly better than that of binary search

• The relative complexity of ternary and binary search depends on the distribution of values across the array

Suppose we do merge sort with a five-way split: divide the array into 5 equal parts, sort each part and do a 5 way merge. What would the worst-case complexity of this version be?

• O(n²)

• O(n² log₅n)

• O(n log₂n)

• O(n (log₂n)²)

The brute force algorithm for solving the traveling salesman problem is________________

• Approximate and Efficient

• Optimal and Inefficient

• Optimal and Efficient

• Approximate and Inefficient