tags:
- cs321
- school
- bsu
- book
- notes
- algorithms
- data-structures
created: 2024-10-14Which sorting algorithm is faster once the input size
Once the input size
What is the worst-case running time of insertion sort?
The worst-case running time of insertion sort is. What is the worst-case running time of merge sort?
The worst-case running time of merge sort is.
How often is the extra precision of determining the exact running time of an algorithm useful?
The extra precision of determining the exact running time of an algorithm is rarely useful.
What happens as to the multiplicative constants and lower-order terms of an exact running time as the input size grows?
As the input size grows, the multiplicative constants and lower-order terms of an exact running time are dominated by the effects of the input size itself.
What are you studying when you look at input sizes large enough to make only the order of growth of the running time relevant?
When you look at input sizes large enough to make only the order of growth of the running time relevant, you are studying asymptotic efficiency.
For what inputs is an asymptotically efficient algorithm the best choice for?
An asymptotically efficient algorithm is the best choice for all but very small inputs.
...
Of the two sorting algorithms, insertion sort and merge sort, merge sort is faster once the input size is large enough. Insertion sort is still faster for smaller input sizes.
Insertion sort:
Merge sort:
Even though you're able to determine the exact running time of an algorithm using the method from last chapter, that kind of precision is rarely necessary. The reason is because the effects of the lower order terms and constants are overwhelmed by the dominant term in the equation.
When you're analyzing an algorithm with inputs that tend towards being infinitely large, you are studying the asymptotic efficiency of it. The reason you want to study the asymptotic efficiency of an algorithm is because the ones that are asymptotically efficient are usually the best choice for all but very small inputs. In the real world, algorithms tend to work with very large input sizes, or input sizes of varying size.
...
What does O-notation characterize?
O-notation characterizes an upper bound on the asymptotic behavior of a function.
What does O-notation say about a function?
O-notation says that a function grows no faster than a certain rate based on the highest-order term.
What is the rate of growth of the function
The rate of growth of the function
How would you write the O-notation for the function
?
You would write the O-notation for the functionas .