COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
When n is large, the other terms become insignificant
|
|
When n is small, the other terms are significant.
|
|
When the algorithm completes running, the decimals don’t matter
|
|
When computer programmers are tired, they don’t like to think about math
|
Detailed explanation-1: -Big-O notation doesn’t care about constants because big-O notation only describes the long-term growth rate of functions, rather than their absolute magnitudes.
Detailed explanation-2: -Note that the big-O expressions do not have constants or low-order terms. This is because, when N gets large enough, constants and low-order terms don’t matter (a constant-time algorithm will be faster than a linear-time algorithm, which will be faster than a quadratic-time algorithm).
Detailed explanation-3: -The time complexity of this algorithm can be classified as O(n), meaning that, as n increases, the run time increases linearly. We can ignore the if statement inside the for loop, as its time complexity O(1) isn’t strongly dependent on the input size.
Detailed explanation-4: -Recall that when we use big-O notation, we drop constants and low-order terms. This is because when the problem size gets sufficiently large, those terms don’t matter. However, this means that two algorithms can have the same big-O time complexity, even though one is always faster than the other.