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
        
    • 
      

Assertions

• 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
    
•