Java tutors in the USAJava is a computing language designed for the development of desktop and mobile applications, embedded systems, and the processing of big data. Introduced in 1995, Java is so much like C and C + + but easier to use because it enforces the object-oriented programming model. One ...

## Runtime Complexity of Java Code

**Adding/removal scenario:**

- INPUT: MultiSet with size/2 elements;
- Adding ratio*size random elements to multiset;
- Removing size-ratio*size random elements from multiset.

**Adding/search scenario:**

- INPUT: MultiSet with size/2 elements;
- Adding ratio*size random elements to multiset;
- Searching size-ratio*size random elements from multiset.

#### LinkedList multiset

- Best case: we can add only a small number of integers many times. In this case, the complexity is “almost” constant;
- Worst case: every added integer is new for the multiset. So, we must look through the list every time. Strictly O(N).

- Best case: we remove elements from the “small” set of integers. The same as for adding: “almost” constant.
- Worst case: each time we try to remove the element, which is not in the multiset. We look through the whole list – O(N).

#### SortedLinkedList multiset

- Best case. We add new elements every time in descending order (if the list is sorted in ascending order). In this case every time we will put an element to the beginning of the list – so the complexity of each operation is O(1) (constant).
- Worst case. We add new elements every time in ascending order (if the list is sorted in ascending order). In this case every time we will put an element to the end of the list. To make it we need O(N) time.

- Best case. We remove elements in ascending order(if the list is sorted in ascending order). In this case every time we will delete the start element of the list – so the complexity of each operation is O(1) (constant).
- Worst case. We delete elements every time in descending order (if the list is sorted in ascending order). In this case every time we will delete the finishing element of the list. To make it we need O(N) time.

#### BinarySearchTree multiset

- Best case. In the best case, we add elements in such a way, that every time we have a balanced tree, so the height of the tree equals logN.
- Worst case. In the worst case, we obtain a binary tree with height N. We can get such a tree, for example, by adding elements in ascending order: every time a new element will be the right son of the right-most leaf.

- Best case. The node deletion does not happen. We just decrease node labels. In this case, we can execute the operation in h steps (or even less).
- Worst case. Every time we delete the node from the tree.

- Best case. The tree is balanced. Complexity is O(logN).
- Worst case. A tree is a chain. Complexity is O(N).

#### BalancedTree multiset

- Best case. In the best case, we don’t need to create an additional node in the tree – just increase the node label.
- Worst case. Each time creating a new node.

- Best case. In the best case we don’t need to delete the node from the tree – just decrease the node label.
- Worst case. Each time deleting a new node.