Which of the following specific run-time estimates would reduce to the highest r

Question

Which of the following specific run-time estimates would reduce to the highest run-time complexity?

(a) 1000(N^3) (b) 100000 (log N) + N^2 (c) (3^N/ 1000)- N (d) 10(N^2) + 500N + 999 (N /2)

What is the time complexity for retrieving the element in the middle of a doubly-linked list of N elements?

(a) O(1) (b) O(log N) (c) O(N) (d) O(N log N)

What is the run-time complexity of the following function?

def c1(N):

ret = 1

for i in range(N//2, N):

ret *= i

return ret

(a) O(log N) (b) O(N) (c) O(N log N) (d) O(N2)

Explanation / Answer

1) Answer : (c) (3^N/ 1000) - N

Explanation: Lets express all complexity in big-O

(a) 1000(N^3) = O(N3)

(b) 100000 (log N) + N^2 = O(N2)

(c) (3^N/ 1000) - N = O(3N)

(d) 10(N^2) + 500N + 999 (N /2) = O(N2)

Now O(N3) takes more time than O(N2) , but O(3N) takes more time than O(N3). As exponential time complexity grows much faster than polynomial.

2) Answer : (c) O(N)

Explanation: We nee to travel atleast N/2 nodes. This takes O(N/2) time which is equlas to O(N)

3) Answer : (b) O(N)

Explanation : complexity of given function is same as the complexity of "for" loop in it as all other operations takes only constant time. Here for loop executes from N/2 to N, which is N/2 times, complexity becomes O(N/2) = O(N).

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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