30 Questions
What is the primary factor that determines the efficiency of a computer system?
The quality of the algorithm used
What is the time complexity of the sorting algorithm used on computer A?
n2
How much faster is computer A than computer B in terms of raw computing power?
1000 times
What is the approximate time taken to sort an array of 10 million numbers on computer A?
More than 5.5 hours
What is the time complexity of the sorting algorithm used on computer B?
n lg n
What is the approximate time taken to sort an array of 10 million numbers on computer B?
Under 20 minutes
What is the form of the linear function of n?
an+b
Why do we focus on the worst-case running time?
Because it gives a guaranteed upper bound on the running time
What happens to the lower-order terms when analyzing the order of growth?
They are dropped
What is the order of growth of the worst-case running time of insertion sort?
n2
What does the notation Θ(n2) represent?
The running time grows like n2
When does the worst-case running time of an algorithm often occur?
When the item being searched for is not present
What is the name of the method that involves guessing the form of the solution and then verifying it through induction?
Substitution method
What is the purpose of the inductive hypothesis in the substitution method?
To apply the solution to smaller values
What is the recurrence equation given in the text?
T(n) = 4T(n/2) + n
What is the height of the recursion tree for the recurrence T(n) = 3T(n/4) + cn^2?
log4n
What is the purpose of constructing a recursion tree?
To determine the total cost of all levels of recursion
What is the sub problem size at depth i in the recursion tree for the recurrence T(n) = 3T(n/4) + cn^2?
n/4i
Why do inefficient sorting algorithms like selection sort make redundant comparisons?
Because their outcome has already been determined by earlier comparisons
What is the purpose of converting a sorting algorithm into a decision tree?
To determine the maximum number of comparisons made by the algorithm
What is the relationship between T(n) and the height of the decision tree?
The height of the decision tree is equal to T(n)
What is the maximum number of different final actions that a sorting algorithm can take?
2T(n)
What is the purpose of A(n) in the context of sorting algorithms?
To represent the number of different final actions the algorithm can take
How many possible actions must any sorting algorithm distinguish between?
n!
What is the minimum number of different actions required by an algorithm to sort ndistinct numbers?
n!
What is the relationship between A(n) and n! in the context of sorting algorithms?
A(n) >= n!
What is the lower bound on the worst-case running time of a comparison-based sorting algorithm?
n log n
What is the purpose of Stirling's approximation in the context of sorting algorithms?
To provide a lower bound on the time complexity
What is the correct sorted order of the array a = {5, 3, 2, 9}?
{2, 3, 5, 9}
What is the generalization of the lower bound on sorting algorithms?
It can be applied to a number of other problems
Compare the performance of two computers with different sorting algorithms, one with a time complexity of n^2 and the other with a time complexity of n log n. Which one will sort an array of 10 million elements faster?
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
