DAA FT REVIEWER

big O notation

• mathematical tool to measure algorithm efficiency

• describes how running time grows with input size

• focuses on worst-case performance

• ignores machine-specific details

• O(I) - constant time

• O (log n) - logarithmic time

• O(n) - linear time

• O (n log n) - linearithmic time

• O(n²) - quadratic time

• O (2^n), O(n!) - exponential/factorial

common big-O classes

constant time O (I)

• runtime does not grow with input size

• operations take the same time regardless of n

logarithmic time O(log n)

• input is repeatedly divided

• very efficient for large inputs

linear time O(n)

• work grows directly with input size

• processes each element once

linearithmic time O(n log n)

• common for divide and conquer

• faster than quadratic, slower than linear

quadratic time O(n²)

• caused by nested loops

• work grows with the square of input size

exponential time O(2^n)

• work doubles for every additional elements

• very slow for large inputs

factorial time O(n!)

• grows extremely fast

• common in brute force

omega notation

• Ω describes a lower bound

• guarantees the runtime is at least f(n)

• used to highlight minimum possible performance

theta notation

• Θ gives a tight bound

• Describes the exact growth rate

• Used when best and worst cases are in the same order of magnitude

best case

• Fastest possible execution​

• Minimum operations​

• Represented using Ω​

average case

• Expected performance across typical inputs​

• Balanced view​

• Represented using Θ​

worst case

• Slowest possible scenario​

• Maximum operations​

• Represented using O​

space complexity

• measures memory usage:

  • variables

  • temporary structures

  • recursion depth

input space

memory needed to store input itself

auxiliary space

extra memory required by the algorithm

output space

memory required to store the result