Big-O Notation

1. Primitive Operations

• Basic computations
  • evaluating an expression, assigning a value to a variable, indexing into an array, calling a method, returning from a method and etc
• Assumed to take a constant amount of time in th RAM model

2. Run time

• Time that is going to take depends on the inputs
• There can be the best case and the worst case and the runtime will be bounded by these two
• The runtime can change depending on the environment, but its growth rate stays the same
• The growth rate is not affected by constant factors or lower-order terms!

3. Big-O Notation

**Given functions f(n) and g(n), we say that f(n) is O(g(n))

if there are positive constants c and n0 such that $f(n)\leq cg(n)$ for n ≥ n0**

• Big-O Notation gives an upper bound on the growth rate of a function
• "f(n) is O(g(n))" means that the growth rate of f(n) is no more than the growth rate of g(n)

Rules

• If f(n) : a polynomial of a degree d → f(n) is O(n^d)