2.3.1 Analysis, design, comparison of algorithms

• What are the two main aspects to check when developing an algorithm?

  Time Complexity and Space Complexity
• What does time complexity measure in an algorithm?

  Time required to solve a problem
• What notation is used to express time complexity?

  Big-O notation

  
• What does Big-O notation indicate about an algorithm?

  Upper limit of time taken

  
• How does time complexity help in algorithm analysis?

  Predicts time based on input size
• What is the general form of Big-O notation?

  O(n)

  
• What are the different types of Big-O notations and their descriptions?

  • O(1): Constant time complexity
  • O(n): Linear time complexity
  • O(n²): Polynomial time complexity
  • O(nn): Polynomial time complexity
  • O(2n): Exponential time complexity
  • O(log n): Logarithmic time complexity

  
• What does O(1) signify in time complexity?

  Independent of input size

  
• What does O(n) signify in time complexity?

  Proportional to the number of elements
• What does O(n²) signify in time complexity?

  Proportional to the square of elements
• What does O(2n) signify in time complexity?

  Time doubles with each additional item

  
• What does O(log n) signify in time complexity?

  Increases at a smaller rate
• How should one approach calculating time complexity?

  Think logically through the algorithm
• What are the key considerations when designing algorithms?

  • Complete the task effectively
  • Optimize for time complexity
  • Optimize for space complexity
  • Balance between time and space complexities
• What should you focus on if processing speed is crucial in a large database?

  Time complexity
• What should you focus on if you have ample processing power?

  Space complexity
• How can you reduce space complexity?

  Perform changes on original data
• How can you reduce time complexity?

  Reduce the number of embedded loops
• What is the Big-O notation for a linear search algorithm?

  O(n)

  
• What is the Big-O notation for a binary search algorithm?

  O(log n)

  
• What is the Big-O notation for a bubble sort algorithm?

  O(n²)

  
• What does the linear search algorithm do?

  Traverses through every item one at a time
• What is the structure of the linear search algorithm?

  Single while loop
• What does the binary search algorithm do?

  Splits the list into smaller lists
• What is the structure of the binary search algorithm?

  While loop with midpoint calculation
• What does the bubble sort algorithm do?

  Evaluates pairs of items in the list
• What is the structure of the bubble sort algorithm?

  While loop with item comparisons
• How do the time complexities of linear search, binary search, and bubble sort compare?

  • Linear Search: O(n)
  • Binary Search: O(log n)
  • Bubble Sort: O(n²)
• What are the key differences between time complexity and space complexity?

  • Time Complexity: Measures execution time
  • Space Complexity: Measures memory usage
  • Both are important for algorithm efficiency