Thursday, January 24, 2008

Algorithm assessment

  • Is the algorithm running in constant time?
    • Runs the same amount of time no matter when 'n' is
    • O(1)
      • No loops or constant time loops
  • Linear time
    • Does the problem run exactly proportional to the size of 'n'?
    • Dominant single loop dependant linearly on n
  • Logarithmic
    • The algorithm divides the size of the problem by a constant
      • Runs in O(log n)
        • Dominant single lop is a divide by 2 on each iteration


  • Boolean expressions or predicates that evaluate to true or false
  • In a program they express constraints on the state that must be true at that point
  • Associate with
    • Individual program statements
    • Functions
    • Classes
  • Specify clearly, precisely and succinctly
    • What is expected and guaranteed by each component
      • Class function and statement
    • The essence of documentation
    • Essential for debugging
    • Aids in fault tolerance
  • Result
    • Result of a query but only in ensure assertions
  • Current
    • @ Current object
  • Void
    • Not attached
  • Name
    • Value of the variable name before a routine starts
  • Name'
    • Value of the name after a routine terminates
    • Alternate name 'old name' instead of Name'
  • **study textual notation**
    • From online notes, cannot type all this

No comments: