What is it

Array is a contiguous memory.

Concepts

When an input is an array, clarification whether the array is a sorted or unsorted is a critically important time complexity assumption to question/clear.

Time Complexity

Merge Sort

Merge sort has Big O = Big Omega = Big Theta of O(n log n).

Sum of All Comparison

Sum of all comparison (n-1) + (n-2) + (n-3) + …+1 is n*(n-1)/2.

• This would translate to a time complexity of O(n^2).

Questions to ask during interview when it involves array

Is the array sorted?

What is the element types of the array?

Is there an empty or null value in the array?