Data Structures and Algorithms in Python by Grow with Google on Coursera.
Efficiency (computational complexity) is how well you are using the computer's resources to get the job done.
Lists are collections where the elements have an order.
Unlike lists, an array has a location called an index—a number associated with that place in the array. Each element stores a value and an index.
Behind the scenes a Python list is built as an array but there's a lot of code built in to the Python language running to make that operation possible. Since Python is a "higher level" programming language, there's a lot of code built into the infrastructure that causes your code to actually run much more slowly than you'd think.
Linked lists have an order, but there are no indices. Each element stores a value and a pointer to the next element, so adding and removing elements is more efficient than in an array.
Stacks are list based data structures where elements are added and removed from the beginning of the list or the top of the stack. Stacks are "last in first out."
Queues are list based data structures where elements are added to the end of a list and removed from the beginning of the list. Queues are "first in first out."
Compare the target value to the middle element of the list. If they are not equal, the half in which the target cannot lie is eliminated and the process is repeated on the remaining half.
Efficiency of binary search is .
Repeatedly iterate through a list comparing adjacent elements and swapping them if they are in the wrong order.
Efficiency of bubble sort is . Space complexity is . Naive approach.
Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted). Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining.
Efficiency of merge sort is . Auxiliary space is .
Select a "pivot" element from the array and partition the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.
Efficiency of quick sort is . Space complexity is .