Week 1

• Abstract Data Types (ADT)


  High-level descriptions of data structures focusing on operations rather than implementations (e.g., stacks, queues)
• Space Usage


  The amount of memory an algorithm or program requires to execute
• Complexity


  Measures how the time or space usage of an algorithm grows as the input size increases
• Primitive Operations


  Basic operations an algorithm performs, like comparisons or assignments. These should take constant time in the RAM model
• Complexity Scenarios


  • Best-case
  • Average-case
  • Worst-case
• Run Time


  The time taken by a program or algorithm to complete execution
• Big-O Notation


  A mathematical notation describing the upper bound or worst-case complexity of an algorithm in terms of the input size
• Logarithmic Complexity, O(log n)

  • Complexity where the performance grows logarithmically with the input size
• Linear Complexity, O(n)


  • Complexity where the performance grows linearly with the input size
• Quadratic Complexity, O(n2)


  • Complexity where the performance grows quadratically with the input size
• Linarethmic complexity, O(n log n)

  • Complexity often seen in efficient sorting algorithms like Merge Sort or Heap Sort
• Cubic Complexity, O(n3)


  • Complexity where the performance grows cubically with the input size
• Exponential Complexity, O(2n)


  • Complexity where the performance grows exponentially with the input size
• Simplifying Functions in Big-O Notation

  Rules to simplify expressions describing complexity, like dropping lower-order terms or constants