[go: up one dir, main page]
Scribd
Upload
122 views2 pages

DAA Quiz 1

The document contains a 10 question quiz about data structures and algorithms. It covers topics like time complexities of sorting algorithms like quicksort, mergesort, and selection sort as well as the time complexities of different functions.

Uploaded by

cihel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
122 views2 pages

DAA Quiz 1

The document contains a 10 question quiz about data structures and algorithms. It covers topics like time complexities of sorting algorithms like quicksort, mergesort, and selection sort as well as the time complexities of different functions.

Uploaded by

cihel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

DAA QUIZ TEST

Duration: 30 Minutes
1. What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?
a. Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)
b. Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)
c. Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)
d. Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)

2. What is time complexity of fun()?


int fun(int n)
{
int count = 0;
for (int i = 0; i < n; i++){
for (int j = i; j > 0; j--){
count = count + 1;
}}
return count;
}
a)theta(n^2) b)theta(nLogn) c)theta(n) d)theta(nLognLogn)
3. Which of the following is not O(n^2)?

a)(15^10) * n + 12099 b)n^1.98 c)n^3 / (sqrt(n)) d)(2^20)*n

4. Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2,
f3 and f4?

f1(n) = 2^n
f2(n) = n^(3/2)
f3(n) = nLogn
f4(n) = n^(Logn)

a)f3, f2, f4, f1 b)f3, f2, f1, f4 c)f2, f3, f1, f4 d)f2, f3, f4, f1

5. The following statement is valid. log(n!) = (n log n).

a)True b)False

6. Which of the following sorting algorithms has the lowest worst-case complexity?

a)Merge Sort b)Bubble Sort c)Quick Sort d)Selection Sort

7. You have an array of n elements. Suppose you implement quicksort by always choosing the central
element of the array as the pivot. Then the tightest upper bound for the worst case performance is

a)O(n2) b)O(nLogn) c)Theta(nLogn) d)O(n3)

8. To determine the efficiency of an algorithm the time factor is measured by:

a)Counting micro seconds b)Counting number of key operations


c)Counting number of statements d)Counting kilobytes of algorithm

9. Which of the following is asymptotically smaller?


a)lg(lg*n) b)lg*(lgn) c)lg(n!) d)lg*(n!)

10. Give the correct matching for the following pairs:

A. O(log n) 1. Selection sort

B. O(n) 2. Insertion sort

C. O(nlog n) 3. Binary search

D. O(n^2) 4. Merge sort

codes:
A B C D
a. 3 1 2 4
b. 3 1 4 2
c. 1 3 4 2
d. 1 4 3 2

You might also like