A growth-rate function is a mathematical function used to indicate an algorithm\

Question

A growth-rate function is a mathematical function used to indicate an algorithm's time efficiency in terms of the size of the problem.

a. True
b. False

If a problem of size n requires time that is directly proportional to n, the problem is ______.

a. O(1)
b. O(n)  
c. O(n2)  
d. O(log2 n)  

   
The recursive binary search algorithm is a logarithmic algorithm.

a. True
b. False

Which of the following growth-rate functions indicates a problem whose time requirement is constant?

a. 1
b. n
c. n2
d. log2 n

Explanation / Answer

The running time of an algorithm grows with respect to the size of input. The size of the mathematical function is directly propotional to running time.

Option a.True is correct.

If a problem of size n requires time that is directly proportional to n, the complexity is O(n).

Option b.O(n) is correct.

Binary search is perfomed by taking sorted collection of data. Binary searching applied to a data which allows random access, the worst case complexity of recursive binary search tree : O(log(n) but in some situations it is O(log(n)+1).

The statement is true.

Growth-rate functions indicates a problem whose time requirement is constant is O(1)=1

Therefore option a is correct.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.