1. What does computational complexity measure? Choose One 5 points O The amount
ID: 3147482 • Letter: 1
Question
1. What does computational complexity measure? Choose One 5 points O The amount of time and memory required to solve a problem The amount of logic gates required in a circuit The number of messages that need to be transmitted to solve a problem O Whether a problem requires Calculus to reach a solution 2 Functions with the Slowest Growth Group 4 questions 2.1 Which of these functions grows the most slowly? Choose One 5 points This is also asking which is the most efficient algorithm? f(n) = n! f(n)-2 f(n) = log n f(n) = nExplanation / Answer
1. The computational complexity is a measure of how many steps are required in the worst case to solve an input of a given size.
Hence, the correct option is the THIRD OPTION.
2.1 log(n) grows much slower than n. while the other two options being of exponential behaviour will increase at a much higher rate than n or log(n). n! outgrows an exponential function with a constant base.
ORDER OF GROWTH RATE: log(n) < n < 2n < n!
Hence, the correct option is the THIRD OPTION
2.2 log(n) grows slower than n. This implies that n*n will grow faster than n*log(n) while n*log(n) will indeed grow faster than n. 2n being an exponential function is the fastest growing of them all.
ORDER OF GROWTH RATE: n < n*log(n) < n2 < 2n
Hence, the correct option is the FIRST OPTION
2.3 Again, log(n) grows slower than n. also n*log(n) is slower than n2. However, both are faster than n or log(n).
ORDER OF GROWTH RATE: log(n) < n < n*log(n) < n2
Hence, the correct option is the FOURTH OPTION.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.