Notes and Questions

1) Bubble Sort: A simple comparison-based algorithm that repeatedly swaps adjacent elements if they are in the wrong order until the entire list is sorted. Time complexity is O(n^2) in the worst case and space complexity is O(1).

2) Insertion Sort: Another simple algorithm that builds the final sorted list one item at a time by inserting each element into its proper place within a partially sorted list. Time complexity is O(n^2) in the worst case and space complexity is O(1).

3) Selection Sort: A sorting algorithm that sorts an array by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning. Time complexity is O(n^2) in the worst case and space complexity is O(1).

4) Radix Sort: A non-comparison based algorithm that sorts data by processing individual digits or groups of digits in each element. Time complexity is O(d(n+k)), where d is the number of digits in the largest number and k is the range of possible values for each digit, and space complexity is O(n+k).

5) Counting Sort: Another non-comparison based algorithm that works by counting the number of occurrences of each value and using that information to place the elements in order. Time complexity is O(n+k), where k is the range of possible values, and space complexity is O(n+k).

Why is time and space complexity important when choosing an algorithm?

Time and space complexity are important considerations when choosing an algorithm because they give an estimate of how much time and memory resources an algorithm will require to execute on a given input size.

Should you always use a constant time algorithm / Should you never use an exponential time algorithm? Explain?

No, because each different situation has a more efficient sorting algorithm. And some of these situations may require the exponential algorithm.

What are some general patterns that you noticed to determine each algorithm's time and space complexity?

Different Branching and conditionals, nested loops, recursion, and dynamic programing.

a = 0
b = 0
for i in range(N):
  a = a + random()
 
for i in range(M):
  b= b + random()

answer: 3, O(N + M) time, O(1) space