Finding the Time Complexity – Worst Case (Big-Θ) – Array List, BST


Hi I’m a bit confused on how to find the time complexity of the following in the worst case in terms of big-Θ, I’ve figured out 1 and 2.

What is the worst-case time complexity, in terms of big-Θ, of each of these operations: (1) insert an element in the array list = Θ(1) (2) remove an element from the array list (e.g. remove an occurrence of the number 5) = Θ(n)

(3) remove the second element from the array list (i.e. the one in position 1)

(4)count the number of unique elements it contains (i.e. the number of elements excluding duplicates; e.g.[6,4,1,4,3] has 4 unique elements)

Suppose you have an initially empty array list with an underlying array of length 10. What is the length of the underlying array after:

(5) inserting 10 elements in the array list (6) inserting 10 more elements in the array list (i.e. 20 elements in total) (7) inserting 10000 more elements in the array list (i.e. 10020 elements in total)

What is the worst-case time complexity, in terms of big-Θ, of each of these operations on binary search trees: (8) add an element in the tree (assuming that the tree is balanced) (9) add an element in the tree (without assuming that the tree is balanced) (10) find the largest element in the tree (assuming that the tree is balanced) After each operation, we should still have a valid heap.