codeup-java-exercises

BigO Notation

Measuring efficiency:

• Accessing
• Searching
• Inserting
• Deleting

Time Complexity Equation:

• insert size of data-set (n) and return number of operations needed to conduct before function finishes
• always use "worst-case scenario"
• () will contain the function depicting the number of operations needed to complete
• O(1) is an ex. of constant time, where parens holds a constant w/o variables. Not likely, and O(1) is fastest in 1 step
• O(n) linear, 1 for 1 n(size) for m(# computations), is great, anything lower is phenom (log2 n, or O(1))
• (n log n) just above O(n) as next worse
• O(n^2) poly and O(2^n) expo are the most inefficient, expo the worst, both expo in structure. Only factorial is worse than expo

Examples:

•  Constant i = 0; while i < 100 do i += i;
  

•  Linear i = 0; while i < n do i += 1;
  

•  Quadratic for (int i = 0; i < n; i += 1) { for (int j = 0; j < n; j += 1) {
  

  f(n) = n * n = n^2, O(f(n)) = O(n^2)