Question on Time Complexity

Question. Imagine it takes 1 second to sort 1000 elements. How long does it take to sort 10 000 elements assuming your sorting algorithm time complexity is proportional to
a) n^2
b) n log n

Answer a) 

Complexity is proportional to

10,000 * 10,000 / 1000 * 1000 = 100

=> sorting 10,000 items takes 100 seconds

Answer b)

Complexity is proportional to

(10,000 * log_2 (10,000)) / (1000 * log_2 (1000))

Use the change of base rule [log_a (b) = log_c (b) / log_c (a)]

=> log_2 10,000 = log_10 (10,000) / log_10 (2)
and log_2(1000) = log_10 (1000) / log_10(2)

=> (10,000 * log_2 (10,000)) / (1000 * log_2 (1000))
= 10 * (log_10 (10,000) / log_10 (1000)) = 10 * 4/3

ArrayList vs LinkedList implementations in Java

LinkedList and ArrayList are two non-synchronized implementations of the List<> interface in java.

ArrayList > LinkedList

• The main benefit of using an arraylist is that the get by index method operates in O(1) time rather than in O(n) time as with a LinkedList. 

LinkedList > ArrayList

• Iterator.remove and Iterator.add methods can be executed in O(1) time rather than in O(n-index) as with an ArrayList. Therefore a LinkedList implementation should be used if either of these methods will be called frequently. 
• When an ArrayList fills up, a new, larger backing array must be created and all the values copied into the new array. This can be an expensive operation.  Arrays backing the ArrayList can only increase in size, so if there is a sudden anomalous spike in the number of objects stored in an ArrayList, there can be a lot of wasted memory allocation with a sparsely filled backing array. Therefore, if there is going to be fluctuation in the size of the list, you should consider using a LinkedList. 

Summary Table showing common list methods: