4.4 Theory of Computation

• What 2 forms of complexity can a algorithm be measured in?

  In terms of space and time complexity
• What is the ideal characteristic of an algorithm?

  Runs quickly and uses little space
• What are the types of graphs related to algorithm complexity?

  • Constant function
  • Logarithmic function
  • Linear function
  • Polynomial function
  • Exponential function
  • Factorial function

  
• What does Big O notation describe?

  The complexity of an algorithm
• What does Big O notation assume?

  A worst-case scenario
• In Big O notation, what variable is commonly used to describe input?


  n
• What is the Big O notation for linear time complexity?

  O(n)
• How is the Big O notation simplified for the function n​3​ + 200n​2​ + 1000n + 25?

  It is O(n​3​)
• What are the different complexities of algorithms in Big O notation?

  • Constant: O(C)
  • Logarithmic: O(log​2​(n))
  • Linear: O(n)
  • Linear Logarithmic: O(nlog(n))
  • Polynomial: O(n​2​)
  • Polynomial: O(n​3​)
  • Exponential: O(2​n​)
  • Factorial: O(n!)
• What is an example of a constant time complexity algorithm?

  Determining if a number is odd or even
• What is an example of a logarithmic time complexity algorithm?

  Binary search
• What is an example of a linear time complexity algorithm?

  Linear search
• What is an example of a polynomial time complexity algorithm?

  Bubble sort
• What is an example of an exponential time complexity algorithm?

  Recursively calculating Fibonacci numbers
• What is an example of a factorial time complexity algorithm?

  Travelers problem
• What are the two types of algorithms based on computation limits?

  • Tractable: solvable in a useful time
  • Intractable: theoretically solvable but impractical
• What characterizes a tractable problem?

  Can be solved within a useful period
• What characterizes an intractable problem?

  Cannot be solved within a useful period
• What is a heuristic method?

  An approximate solution to a problem
• What is the Halting problem?

  Determining if an algorithm will finish
• What does the Halting problem demonstrate?

  Some problems cannot be solved by computers