Big-Oh Notation in Algorithms

Asymptotic Notation

• Asymptotic notation describes the behavior of algorithms.
• In CS1, an informal definition was introduced.
• Key components include:
  • Pull leading term
  • Drop constant
• Common notations include Ο (Big-Oh), Θ (Big-Theta), and Ω (Big-Omega).
• These notations deal primarily with running time, but also space requirements.
• Additional notations exist (e.g., w and o) but are beyond the scope of this course.

O-Notation (Big-Oh)

• Used to give an upper bound on a function.
• Formal Definition:
  • O(f(n)) = {T(n): there exist a positive constant c (c > 0) and n0 ≥ 0 such that 0 ≤ T(n) ≤ c * f(n) for all n ≥ n0}
• Meaning:
  • Your running time T(n) has an upper bound that grows at a rate no faster than f(n).

Ω-Notation (Big-Omega)

• Provides a lower bound on a function.
• Formal Definition:
  • Ω(f(n)) = {T(n): there exist a positive constant c (c > 0) and n0 ≥ 0 such that 0 ≤ c * f(n) ≤ T(n) for all n ≥ n0}
• Meaning:
  • Your running time T(n) will never be lower than f(n).

Θ-Notation (Big-Theta)

• Gives a tight bound on a function.
• Formal Definition:
  • Θ(f(n)) = {T(n): there exist positive constants c₁ (c₁ > 0), c₂ (c₂ > 0) and n0 ≥ 0 such that 0 ≤ c₁f(n) ≤ T(n) ≤ c₂f(n) for all n ≥ n0}
• Meaning:
  • The running time T(n) grows at the same rate as f(n).

Examples

• Illustrative examples demonstrating the application of these notations are included in the text.
• These examples showcase how function behavior is measured to determine computational complexities.
• The steps and reasons for these demonstrations are shown in the text.

B-Trees

• A balanced search tree structure used for secondary storage (e.g., disk).
• Each node in the tree holds many keys and children and has special properties.
  • Every node x has x.n keys such that x.key1 ≤ x.key2 ≤ ... ≤ x.keyx.n
• Keys are sorted.
  • Every node except the root has at least t-1 keys.
• Nodes have a fixed maximal key and child number. -Every node has ≤ 2t - 1 keys.
• B trees use a minimum degree (t) --Every node has to have at least a minimum number of keys and children where t is a positive integer (>= 2)
• Height of a B tree is O(log n) , and has constant branching factor (meaning average number of children per node).

Data Structures on Secondary Storage

• Primary memory uses silicon chips
• Secondary memory consists of magnetic storage such as tapes and disks.
• Disks are cheaper and have a higher capacity.
• Disk access times are slower than memory access times.

Disk Drives

• Average disk access time ranges from 8 to 11 milliseconds.
• Average main memory access time is around 50 nanoseconds.
• Information on disks is divided into pages, with page sizes ranging from 2^11 to 2^14 bytes.
• Disk reads and writes often target single or multiple pages.

B-Tree Applications

• Operating systems use B-trees to manage pages on the disk as a way to handle large amounts of data outside the main memory.

Exponential Identities

• For all real a > 0, m, and n, we have the identities:
  • a⁰ = 1
  • a¹ = a
  • a⁻¹ = 1/a
  • (aᵐ)ⁿ = aᵐⁿ
  • aᵐaⁿ = aᵐ⁺ⁿ

Growth of Functions

• Visualizes the increasing rate and complexity of different mathematical functions.
• Categories functions and their respective growth rates. -- Examples include constant, logarithmic, linear, linearithmic, quadratic, cubic, exponential, and factorial functions.

Recurrences (Master Theorem)

• Analyzing recursive algorithms by calculating their running time.
• The Master Theorem provides a framework to solve certain types of recurrences.

Backtracking

• Algorithms for identifying all solutions or optimal solutions to combinatorial problems.
• Employ a tree-search based methodology.
• Backtrack (return step) occurs if a solution is not complete.
• This method is effective to find possible solutions or determine if a solution exists

Running Time Analysis

• The calculation of the run time
  • Recursion tree and substitution method are two techniques that can be used to find the solution

The Skeleton Backtracking Algorithm

• Method structure representing backtracking principles

Problem Definitions

• Clear explanations of problems like N-Queens or subset sum are included in the text.