Abstract


  • Analysis space & time used, related with the input size and observing the trend when input size gets bigger
  • The analysis isn’t limited to particular machine. It applies to all the machines

Asymptotic Analysis


  • Asymptotic Analysis doesn’t return some good approximations of the time the program takes to run. We mean the time taken by the program bounded by some constant a function when the input size is bigger than a certain constant
  • represents the upper bound
  • represents the space in between upper bound and lower bound
  • represents the lower bound

Determine tightest upper bound (in terms of )

  1. Take the most dominant term and drop the coefficients
  2. If 2 terms with multiplying each other, they are one piece

Worst Space Complexity

2 ways to count

Maximum space every allocated at one time

  • The amount of space the algorithm needs to run

Total space ever allocated

  • The total amount of space algorithm uses to run the algorithm. We need to consider this because memory allocation is an expensive operation

Worst Time Complexity

  • The time it takes relative to the input size

References