For each of the following T(n), write the corresponding Big O time complexity. 1

Question

For each of the following T(n), write the corresponding Big O time complexity.

11. What is the time complexity to insert or remove an item in the middle of an ArrayList? Why? My answer and correct if wrong please : Linear because when you insert or remove in the middle of an ArrayList, the whole ArrayList shifts.

12. What is the average time complexity to an item to the end of an ArrayList? My answer and correct if wrong please : constant

14. Taking this all into account, what situations would an ArrayList be the appropriate data structure for storing your data?

https://gyazo.com/dbbe398d0bb3b152594a0a09408459e4

16. What is the space complexity of the above algorithm? In other words how much space is used up based on the input size?

https://gyazo.com/4c93cdd693b82a2e98ba5b2b384a48f5

Explanation / Answer

1) Yes the answer provided is right as we will eliminate 2 as its constant and 3n will be O(n) which will be covered by O(n^2)

2) T(n) = (n^2+n)(n^2+pi/2)
T(n) = n(n+1) (n^2 + pi/2)
T(n) = n*(n) (n^2) {dropped the constants)
T(n) = n^2 * n^2
Hence it becomes O(n^4)

3) Yes provided answer is correct, as the expression time depends linear on n hence O(n)

4) T(n) = 1^2 + 2^2 + .....+ n^2 , the provided answer is correct , the expression depends linearly on n^2 hence O(n^2)

5) T(n) = 10, correct time taken for constant is O(1)

6) T(n) = 10^100, this is still a constant hence O(1)

7) T(n) = n+ logn, the complexity will be O(n) + O(logn)

8) T(n) = 12log(n) + (n/2)-400
If we drop the constants - T(n) - > logn + n
O(logn) + O(n)

9) T(n) = (n+1) *logn -n
T(n)= nlogn - n
O(nlogn) -O(n)

10) Yes the provided answer and explanation is correct

11) It will be linear as even it is at end you need to traverse through whole array.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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