Notes from CS2040S Week 3 Tutorial

CS2040S_w3t.md

CS2040S Week 3 Tutorial

Notes from CS2040S Week 3 Tutorial

Asymptiotic Analysis

• Big Theta
  • t(n) = Theta(g(n))
  • k1 * g(n) <= t(n) <= k2 * g(n)
• Big O (how bad it can be)
  • t(n) = O(g(n))
  • t(n) <= k * g(n)
• Big Omega
  • t(n) = Omega(g(n))
  • k * g(n) <= t(n)

Searching

• Linear search
  • O(n)
• Binary Search
  • O(logn) (exploits a property of a sequence / array)
  • Used for peak / valley finding problems

Using static in main (or functions in general)

Java's main method has to be declared static becuase the keyword allows it to be called without creating an object of the class where the said main method is defined. If we omit static, Java will successfully compile the program but it won't execute it.

Abstract Class vs. Interface

In interfaces, none of the methods are implemented. In abstract classes, not all methods are implemented while some are.