Big-O Notations

Question 1

For Arrays?

Answer 1

• traverse all spots = O(N)
• search for an item = O(N) or O(Log2N)
• removed any item location unknown = O(N)
• get any item location unknown = O(1)
• add item at the end = O(1)
• add item at the front = O(N)

Question 2

For Single Linked Lists?

Answer 2

• traverse all nodes = O(N)
• search for an item = O(N)
• remove any item location unknown = O(N)
• get any item location unknown = O(N)
• add item at the end O(N)
• add item at the front = O(1)

Question 3

For Double Linked List?

Answer 3

• traverse all nodes = O(N)
• search for an item = O(N)
• remove any item location unknown = O(N)
• get any item location unknown = O(N)
• add item at the end = O(1)
• add item at the front = O(1)

Question 4

For Binary Search Tree

Answer 4

• traverse all nodes = O(N)
• search for an item = O(log2N)
• remove any item location unknown = O(log2N)
• get any item location unknown = O(log2N)
• add item at the end = O(log2N)
• add item at the front = O(1)

Question 5

For ArrayList?

Answer 5

• traverse all spots = O(N)
• search for an item = O(N) or O(log2N)
• remove any item location unknown = O(N)
• get any item location unknown = O(1)
• add item at the end = O(1)
• add item at the front = O(N)

Question 6

For LinkedList?

Answer 6

• traverse all spots = O(N)
• search for an item = O(N)
• remove any item location unknown = O(N)
• get any item location unknown = O(N)
• add item at the end = O(1)
• add item at the front = O(1)

Question 7

For TreeSets?

Answer 7

• add() = O(log2N)
• get() = O(log2N)
• containsKey() = O(log2N)

Question 8

For HashSets?

Answer 8

• add() = O(1)
• get() = O(1)
• containsKey() = O(1)

Question 9

For TreeMap?

Answer 9

• put() = O(log2N)
• get() = O(log2N)
• containsKey() = O(log2N)

Question 10

For Hash Map?

Answer 10

• put() = O(1)
• get() = O(1)
• containsKey() = O(1)