Hacks

  • Record your findings when testing the time elapsed of the different algorithms.
  • Although we will go more in depth later, time complexity is a key concept that relates to the different sorting algorithms.
  • Do some basic research on the different types of sorting algorithms and their time complexity.
    • Insertion Sort: An algorithm that builds the final sorted array one item at a time. It inserts each element into its proper position in the final sorted array. The time complexity of Insertion Sort is also O(n^2).
    • Selection Sort: An algorithm that sorts an array by repeatedly finding the minimum element from unsorted part and putting it at the beginning. The time complexity of Selection Sort is also O(n^2).

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

    • The time complexity of an algorithm refers to the amount of time it takes to execute the algorithm as a function of the input size. In other words, it measures how quickly the algorithm runs as the input size grows larger. An algorithm with a lower time complexity will execute faster than an algorithm with a higher time complexity. When dealing with large input sizes, even small differences in time complexity can have a significant impact on the overall performance of the algorithm.
    • The space complexity of an algorithm refers to the amount of memory space required by the algorithm as a function of the input size. In other words, it measures how much memory the algorithm needs to store and manipulate the input data. An algorithm with a lower space complexity will use less memory than an algorithm with a higher space complexity. When working with limited memory resources, it is important to choose an algorithm with a lower space complexity to avoid memory overflow errors and other performance issues.

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

    • No, you should not always use a constant time algorithm nor should you never use an exponential time algorithm.
    • The choice of algorithm depends on the problem at hand and the size of the input data. Constant time algorithms are generally preferred as they have a time complexity that does not depend on the size of the input data, and thus, they execute in a constant amount of time regardless of the input size. This means that constant time algorithms can be very efficient for small or fixed-sized input data. However, it is not always possible to design a constant time algorithm for every problem, and sometimes constant time algorithms may not be the most efficient option for larger input sizes.
    • On the other hand, exponential time algorithms are generally avoided as they have a time complexity that grows exponentially with the size of the input data. This means that they can quickly become impractical and inefficient for larger input sizes. However, exponential time algorithms may be the only option for some problems, and sometimes they may be the most efficient option for smaller input sizes.

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

    • Constant Time Complexity (O(1)): The time complexity is constant if the number of operations performed by the algorithm remains the same, regardless of the input size. Examples of algorithms with constant time complexity include accessing an element in an array or performing arithmetic operations.
    • Linear Time Complexity (O(n)): The time complexity is linear if the number of operations performed by the algorithm increases linearly with the input size. Examples of algorithms with linear time complexity include iterating over an array or linked list, or searching for an element in an unsorted array.
    • Quadratic Time Complexity (O(n^2)): The time complexity is quadratic if the number of operations performed by the algorithm increases quadratically with the input size. Examples of algorithms with quadratic time complexity include nested loops that iterate over an array or matrix.
    • Logarithmic Space Complexity (O(log n)): The space complexity is logarithmic if the amount of memory used by the algorithm increases logarithmically with the input size. Examples of algorithms with logarithmic space complexity include recursive algorithms that divide the input data into smaller subproblems.

Complete the Time and Space Complexity analysis questions linked below. Practice