Finding an element in an unsorted array of n elements:

O(n).
Must compare with all elements.



Finding an element in a sorted array of n elements:

O(log n).
Can use binary search.



Adding an element to an unsorted array of n elements:

O(1).
Write the element to some appropriate index.



Adding an element to a sorted array of n elements (the resulting array should also be sorted):

O(n).
Need to move O(n) elements to maintain the order.