Algorithms - kenhendricks00/DiscreteMathematics GitHub Wiki

Algorithm

a process or set of rules to be followed in calculations or other problem-solving operations

Features of an Algorithm

  • Input
  • Output
  • Correctness
  • Finiteness
  • Effectiveness
  • Generality
  • Definiteness

Complexity: O(n)

Time Complexity: time required for the program to execute

Space Complexity: memory space required for the program to execute

General rule

constant < log < linear < nlogn < quadratic < cubic < exponential

Examples

Find the complexity for each function

f(n) = 3 + 1/2n

f(n) = O(1)

f(n) = n^3 + 2n

f(n) = O(n^3)

f(n) = logn + nlogn

f(n) = O(nlogn)