Array.unshiftbecause we'll know that the built-in function already has some inherent run-time complexity. (We'll note each of these special cases when they come up.)
listand 8 for
list2! But Computer Science doesn't care- we haven't defined anywhere in our
arrayHasTwofunction or anywhere else about where the 2 might fall inside the array. The worst case performance of this function is still O(n).
arr[len(arr)/2]. This operation does not depend on the size of n, since the array length is readily available and accessing elements in an array by index is a single operation. This algorithm that immediately retrieves the middle element by index runs in O(1) time.
nincreased by 1000+ between the 2 examples, the value of log(n) only increased by roughly 10. Thus log(n_) is significantly less than n at large numbers.
xin a sorted array
x == arr[n/2], return
n/2as the index of x. If
x > arr[n/2], repeat the same process on the right half of arr. If
x < arr[n/2], repeat the same process on the left half of
arr. Read more about binary search here.
O(2ⁿ)complexity (and any
O(Cⁿ)complexity where C is a constant) is the highest order of complexity (without combining it with itself or others above) and typically bad. If you find that your algorithm runs in exponential complexity in a DS&A interview, there is probably a more efficient algorithm to solve the problem.