Was given these time complexity problems I think I understand how to do them, bu

Question

Was given these time complexity problems I think I understand how to do them, but I just want to make sure I'm right and if I am not how to do them!

Here are my answers 5) O(2^n) 6) a) 20 seconds b) 400 seconds

5) Fines for illegal parking in Lower Elbonia are $2. However, the fine is doubled for each day the fine goes unpaid. Write the Big-O notation for this growth rate.

6) Assume that, in the worst case, an algorithm takes 1 second to process 100 elements. How long will it take to process 2,000 elements if the growth rate of the algorithm is

a) O(N)

and

b) O(N^2)

Explanation / Answer

Yes you are right in both the cases :)

5) The fine is double everyday. So it's obvious that after n days it will 2^n.

6) a) The size of the input grew 20 times. As the run time is linear, the total time taken will also grow by 20 times.

b) In this case as the run time is quadratic, the total time taken will grow by 400 times.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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