Asymptotic Analysis

Asymptotic Analysis uses asymptotic ntation (like big-oh) to describe the computational complexity of an algorithm, which is how it consumes computational resources, namely time complexity and space complexity.

Time complexity measures the amount of time an algorithm needs to run as a function of its input size.

Space complexity is taken to mean auxiliary space, which is the extra space or temporary space used by an algorithm during its execution.

• We are concerned with how the space consumtion grows, in asymptotic terms, as the size of the input increases.
• Space complexity = Auxiliary space + Input space
• Recursive calls create a function activiation record (or stack frame) in memory, which requires memory allocation.

Asymptomatic Bounds

When we use Big-Oh to communicate how fast an algorithm is, we give the smallest Big-Oh time (tightest upper bound) we can prove to be true.

Big omega descirbes asymptotic lower bounds. Ω(f(n)) is set of functions that grow no slower than f(n).

When we use Big-Oh/Omega to communicate how fast an algorithm is, we give the tightest upper/lower bound we can prove true.

Big Theta is used to describe asymptotic tight bound. Θ(f(n)) is the set of functions that grow no faster and no slower than f(n)