COP3505 Exam 1 Review PDF

Asymptotic Notation Big-Oh, Big-Omega, and Big-Theta COP 3503 Spring 2025 Department of Computer Science University of Central Florida Dr. Steinberg Asymptotic Notation Asymptotic Notation describes the behavior of algorithms. In CS1,...

Asymptotic Notation Big-Oh, Big-Omega, and Big-Theta COP 3503 Spring 2025 Department of Computer Science University of Central Florida Dr. Steinberg Asymptotic Notation Asymptotic Notation describes the behavior of algorithms. In CS1, you learned the informal definition. Pull leading term Drop Constant There are a total of 3 primary notations that can be used to describe algorithms. In this class we are primarily interested in running time, however asymptotic notation can help understand other aspects such as algorithm’s space requirement (memory). The 3 notations are O, Θ, Ω, FUN FACT: There are an additional two notations, however we won’t cover them in this class. They are more for a graduate level course. The notations are ω and o O-Notation (big-Oh) We use Oh-notation to give an upper bound (asymptotic upper bound) on a function, to within a constant factor. 𝑇 𝑛 =𝑂 𝑓 𝑛 Formal Definition: 𝑂 𝑓 𝑛 = ሼ𝑇 𝑛 : there exist a positive constant 𝑐 ሺ𝑐 > 0ሻ and 𝑛0 ≥ 0 such that 0 ≤ 𝑇 𝑛 ≤ 𝑐 ∗ 𝑓 𝑛 for all 𝑛 ≥ 𝑛0 ሽ What does this mean? This means that your running time 𝑇ሺ𝑛ሻ has an upper bound that grows at a rate no faster than 𝑓ሺ𝑛ሻ. Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 𝑐, 𝑛0 = ? Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 𝑐, 𝑛0 = ? 0 ≤ 3𝑛2 − 6 ≤ 𝑐𝑛4 Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 𝑐, 𝑛0 = ? 0 ≤ 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 3𝑛2 − 6 Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 𝑐, 𝑛0 = ? 0 ≤ 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 3𝑛2 − 6 6 ≤ 3𝑛2 Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 𝑐, 𝑛0 = ? 0 ≤ 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 3𝑛2 − 6 6 ≤ 3𝑛2 6 ≤ 𝑛2 3 Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 𝑐, 𝑛0 = ? 0 ≤ 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 3𝑛2 − 6 6 ≤ 3𝑛2 6 ≤ 𝑛2 3 2 ≤ 𝑛2 Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 𝑐, 𝑛0 = ? 0 ≤ 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 3𝑛2 − 6 6 ≤ 3𝑛2 6 ≤ 𝑛2 3 2 ≤ 𝑛2 2≤𝑛☺ Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 𝑐, 𝑛0 = ? 0 ≤ 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 3𝑛2 − 6 3𝑛2 − 6 ≤ 𝑐𝑛4 6 ≤ 3𝑛2 6 ≤ 𝑛2 3 2 ≤ 𝑛2 2≤𝑛☺ Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 𝑐, 𝑛0 = ? 0 ≤ 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 3𝑛2 − 6 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 𝑐𝑛4 − 3𝑛2 + 6 6 ≤ 3𝑛2 6 ≤ 𝑛2 3 2 ≤ 𝑛2 2≤𝑛☺ Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 𝑐, 𝑛0 = ? 0 ≤ 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 3𝑛2 − 6 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 𝑐𝑛4 − 3𝑛2 + 6 6 ≤ 3𝑛2 𝑐=1 6 ≤ 𝑛2 3 2 ≤ 𝑛2 2≤𝑛☺ Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 𝑐, 𝑛0 = ? 0 ≤ 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 3𝑛2 − 6 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 𝑐𝑛4 − 3𝑛2 + 6 6 ≤ 3𝑛2 0 ≤ 𝑛4 − 3𝑛2 + 6 𝑐 = 1 6 ≤ 𝑛2 3 2 ≤ 𝑛2 2≤𝑛☺ Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 𝑐, 𝑛0 = ? 0 ≤ 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 3𝑛2 − 6 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 𝑐𝑛4 − 3𝑛2 + 6 6 ≤ 3𝑛2 0 ≤ 𝑛4 − 3𝑛2 + 6 𝑐 = 1 6 ≤ 𝑛2 0 ≤ 𝑛2 𝑛2 − 3 + 6 3 2 ≤ 𝑛2 2≤𝑛☺ Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 𝑐, 𝑛0 = ? 0 ≤ 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 3𝑛2 − 6 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 𝑐𝑛4 − 3𝑛2 + 6 6 ≤ 3𝑛2 0 ≤ 𝑛4 − 3𝑛2 + 6 𝑐 = 1 6 ≤ 𝑛2 0 ≤ 𝑛2 𝑛2 − 3 + 6 3 0 ≤ 𝑛2 − 3 2 ≤ 𝑛2 2≤𝑛☺ Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 𝑐, 𝑛0 = ? 0 ≤ 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 3𝑛2 − 6 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 𝑐𝑛4 − 3𝑛2 + 6 6 ≤ 3𝑛2 0 ≤ 𝑛4 − 3𝑛2 + 6 𝑐 = 1 6 ≤ 𝑛2 0 ≤ 𝑛2 𝑛2 − 3 + 6 3 0 ≤ 𝑛2 − 3 2 ≤ 𝑛2 3 ≤ 𝑛2 2≤𝑛☺ Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 𝑐, 𝑛0 = ? 0 ≤ 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 3𝑛2 − 6 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 𝑐𝑛4 − 3𝑛2 + 6 6 ≤ 3𝑛2 0 ≤ 𝑛4 − 3𝑛2 + 6 𝑐 = 1 6 ≤ 𝑛2 0 ≤ 𝑛2 𝑛2 − 3 + 6 3 0 ≤ 𝑛2 − 3 2 ≤ 𝑛2 3 ≤ 𝑛2 2≤𝑛☺ 3≤𝑛☺ Example 1 Show that 3𝑛2 − 6 = 𝑂 𝑛4 𝑐, 𝑛0 = ? 0 ≤ 3𝑛2 − 6 ≤ 𝑐𝑛4 𝑐=1 𝑛0 = 3 0 ≤ 3𝑛2 − 6 3𝑛2 − 6 ≤ 𝑐𝑛4 0 ≤ 𝑐𝑛4 − 3𝑛2 + 6 6 ≤ 3𝑛2 0 ≤ 𝑛4 − 3𝑛2 + 6 𝑐 = 1 6 ≤ 𝑛2 0 ≤ 𝑛2 𝑛2 − 3 + 6 3 0 ≤ 𝑛2 − 3 2 ≤ 𝑛2 3 ≤ 𝑛2 2≤𝑛☺ 3≤𝑛☺ Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 2𝑛2 + 3 ≤ 𝑐𝑛3 Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 2𝑛2 + 3 ≤ 𝑐𝑛3 0 ≤ 2𝑛2 + 3 Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 2𝑛2 + 3 ≤ 𝑐𝑛3 0 ≤ 2𝑛2 + 3 There is nothing left to simplify. With 𝑛 being greater than or equal to 0, we will always get valid values. ☺ Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 2𝑛2 + 3 ≤ 𝑐𝑛3 2𝑛2 + 3 ≤ 𝑐𝑛3 0 ≤ 2𝑛2 + 3 Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 2𝑛2 + 3 ≤ 𝑐𝑛3 2𝑛2 + 3 ≤ 𝑐𝑛3 0 ≤ 2𝑛2 + 3 0 ≤ 𝑐𝑛3 − 2𝑛2 − 3 Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 2𝑛2 + 3 ≤ 𝑐𝑛3 2𝑛2 + 3 ≤ 𝑐𝑛3 0 ≤ 2𝑛2 + 3 0 ≤ 𝑐𝑛3 − 2𝑛2 − 3 𝑐=2 Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 2𝑛2 + 3 ≤ 𝑐𝑛3 2𝑛2 + 3 ≤ 𝑐𝑛3 0 ≤ 2𝑛2 + 3 0 ≤ 𝑐𝑛3 − 2𝑛2 − 3 0 ≤ 2𝑛3 − 2𝑛2 − 3 𝑐 = 2 Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 2𝑛2 + 3 ≤ 𝑐𝑛3 2𝑛2 + 3 ≤ 𝑐𝑛3 0 ≤ 2𝑛2 + 3 0 ≤ 𝑐𝑛3 − 2𝑛2 − 3 0 ≤ 2𝑛3 − 2𝑛2 − 3 𝑐 = 2 0 ≤ 𝑛3 + 𝑛3 − 2𝑛2 − 3 Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 2𝑛2 + 3 ≤ 𝑐𝑛3 2𝑛2 + 3 ≤ 𝑐𝑛3 0 ≤ 2𝑛2 + 3 0 ≤ 𝑐𝑛3 − 2𝑛2 − 3 0 ≤ 2𝑛3 − 2𝑛2 − 3 𝑐 = 2 0 ≤ 𝑛3 + 𝑛3 − 2𝑛2 − 3 0 ≤ 𝑛3 − 2𝑛2 + 𝑛3 − 3 Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 2𝑛2 + 3 ≤ 𝑐𝑛3 2𝑛2 + 3 ≤ 𝑐𝑛3 0 ≤ 2𝑛2 + 3 0 ≤ 𝑐𝑛3 − 2𝑛2 − 3 0 ≤ 2𝑛3 − 2𝑛2 − 3 𝑐 = 2 0 ≤ 𝑛3 + 𝑛3 − 2𝑛2 − 3 0 ≤ 𝑛3 − 2𝑛2 + 𝑛3 − 3 0 ≤ 𝑛3 − 2𝑛2 Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 2𝑛2 + 3 ≤ 𝑐𝑛3 2𝑛2 + 3 ≤ 𝑐𝑛3 0 ≤ 2𝑛2 + 3 0 ≤ 𝑐𝑛3 − 2𝑛2 − 3 0 ≤ 2𝑛3 − 2𝑛2 − 3 𝑐 = 2 0 ≤ 𝑛3 + 𝑛3 − 2𝑛2 − 3 0 ≤ 𝑛3 − 2𝑛2 + 𝑛3 − 3 0 ≤ 𝑛3 − 2𝑛2 2𝑛2 ≤ 𝑛3 Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 2𝑛2 + 3 ≤ 𝑐𝑛3 2𝑛2 + 3 ≤ 𝑐𝑛3 0 ≤ 2𝑛2 + 3 0 ≤ 𝑐𝑛3 − 2𝑛2 − 3 0 ≤ 2𝑛3 − 2𝑛2 − 3 𝑐 = 2 0 ≤ 𝑛3 + 𝑛3 − 2𝑛2 − 3 0 ≤ 𝑛3 − 2𝑛2 + 𝑛3 − 3 0 ≤ 𝑛3 − 2𝑛2 2𝑛2 ≤ 𝑛3 2≤𝑛☺ Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 2𝑛2 + 3 ≤ 𝑐𝑛3 2𝑛2 + 3 ≤ 𝑐𝑛3 0 ≤ 2𝑛2 + 3 0 ≤ 𝑐𝑛3 − 2𝑛2 − 3 0 ≤ 2𝑛3 − 2𝑛2 − 3 𝑐 = 2 0 ≤ 𝑛3 + 𝑛3 − 2𝑛2 − 3 0 ≤ 𝑛3 − 2𝑛2 + 𝑛3 − 3 0 ≤ 𝑛3 − 2𝑛2 0 ≤ 𝑛3 − 3 2𝑛2 ≤ 𝑛3 2≤𝑛☺ Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 2𝑛2 + 3 ≤ 𝑐𝑛3 2𝑛2 + 3 ≤ 𝑐𝑛3 0 ≤ 2𝑛2 + 3 0 ≤ 𝑐𝑛3 − 2𝑛2 − 3 0 ≤ 2𝑛3 − 2𝑛2 − 3 𝑐 = 2 0 ≤ 𝑛3 + 𝑛3 − 2𝑛2 − 3 0 ≤ 𝑛3 − 2𝑛2 + 𝑛3 − 3 0 ≤ 𝑛3 − 2𝑛2 0 ≤ 𝑛3 − 3 2𝑛2 ≤ 𝑛3 3 ≤ 𝑛3 2≤𝑛☺ Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 2𝑛2 + 3 ≤ 𝑐𝑛3 2𝑛2 + 3 ≤ 𝑐𝑛3 0 ≤ 2𝑛2 + 3 0 ≤ 𝑐𝑛3 − 2𝑛2 − 3 0 ≤ 2𝑛3 − 2𝑛2 − 3 𝑐 = 2 0 ≤ 𝑛3 + 𝑛3 − 2𝑛2 − 3 0 ≤ 𝑛3 − 2𝑛2 + 𝑛3 − 3 0 ≤ 𝑛3 − 2𝑛2 0 ≤ 𝑛3 − 3 2𝑛2 ≤ 𝑛3 3 ≤ 𝑛3 3 2≤𝑛☺ 3≤𝑛☺ Example 2 Show that 2𝑛2 + 3 = 𝑂 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 2𝑛2 + 3 ≤ 𝑐𝑛3 𝑐=2 𝑛0 = 2 2𝑛2 + 3 ≤ 𝑐𝑛3 0 ≤ 2𝑛2 + 3 0 ≤ 𝑐𝑛3 − 2𝑛2 − 3 0 ≤ 2𝑛3 − 2𝑛2 − 3 𝑐 = 2 0 ≤ 𝑛3 + 𝑛3 − 2𝑛2 − 3 0 ≤ 𝑛3 − 2𝑛2 + 𝑛3 − 3 0 ≤ 𝑛3 − 2𝑛2 0 ≤ 𝑛3 − 3 2𝑛2 ≤ 𝑛3 3 ≤ 𝑛3 3 2≤𝑛☺ 3≤𝑛☺ Ω-Notation (big-Omega) We use Ω-notation to give a lower bound (asymptotic lower bound) on a function, within a constant factor. T 𝑛 =Ω 𝑓 𝑛 Formal Definition: Ω 𝑓 𝑛 = ሼ𝑇 𝑛 : there exist a positive constants 𝑐 ሺ𝑐 > 0ሻ and 𝑛0 ≥ 0 such that 0 ≤ 𝑐 ∗ 𝑓 𝑛 ≤ 𝑇ሺ𝑛ሻ for all 𝑛 ≥ 𝑛0 ሽ What does this mean? This means that your running time 𝑇ሺ𝑛ሻ will never be lower than 𝑓ሺ𝑛ሻ. Example 1 Show that 3𝑛2 + 2 = Ω 𝑛 Example 1 Show that 3𝑛2 + 2 = Ω 𝑛 𝑐, 𝑛0 = ? Example 1 Show that 3𝑛2 + 2 = Ω 𝑛 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛 ≤ 3𝑛2 + 2 Example 1 Show that 3𝑛2 + 2 = Ω 𝑛 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛 ≤ 3𝑛2 + 2 0 ≤ 𝑐𝑛 Example 1 Show that 3𝑛2 + 2 = Ω 𝑛 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛 ≤ 3𝑛2 + 2 0 ≤ 𝑐𝑛 There is nothing left to simplify. With 𝑛 being greater than or equal to 0 and 𝑐 being positive, we will always get valid values. ☺ Example 1 Show that 3𝑛2 + 2 = Ω 𝑛 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛 ≤ 3𝑛2 + 2 0 ≤ 𝑐𝑛 𝑐𝑛 ≤ 3𝑛2 + 2 Example 1 Show that 3𝑛2 + 2 = Ω 𝑛 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛 ≤ 3𝑛2 + 2 0 ≤ 𝑐𝑛 𝑐𝑛 ≤ 3𝑛2 + 2 0 ≤ 3𝑛2 − 𝑐𝑛 + 2 Example 1 Show that 3𝑛2 + 2 = Ω 𝑛 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛 ≤ 3𝑛2 + 2 0 ≤ 𝑐𝑛 𝑐𝑛 ≤ 3𝑛2 + 2 0 ≤ 3𝑛2 − 𝑐𝑛 + 2 𝑐=3 Example 1 Show that 3𝑛2 + 2 = Ω 𝑛 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛 ≤ 3𝑛2 + 2 0 ≤ 𝑐𝑛 𝑐𝑛 ≤ 3𝑛2 + 2 0 ≤ 3𝑛2 − 𝑐𝑛 + 2 𝑐=3 0 ≤ 3𝑛2 − 3𝑛 + 2 Example 1 Show that 3𝑛2 + 2 = Ω 𝑛 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛 ≤ 3𝑛2 + 2 0 ≤ 𝑐𝑛 𝑐𝑛 ≤ 3𝑛2 + 2 0 ≤ 3𝑛2 − 𝑐𝑛 + 2 𝑐=3 0 ≤ 3𝑛2 − 3𝑛 + 2 0 ≤ 3𝑛 𝑛 − 1 + 2 Example 1 Show that 3𝑛2 + 2 = Ω 𝑛 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛 ≤ 3𝑛2 + 2 0 ≤ 𝑐𝑛 𝑐𝑛 ≤ 3𝑛2 + 2 0 ≤ 3𝑛2 − 𝑐𝑛 + 2 𝑐=3 0 ≤ 3𝑛2 − 3𝑛 + 2 0 ≤ 3𝑛 𝑛 − 1 + 2 0≤𝑛−1 Example 1 Show that 3𝑛2 + 2 = Ω 𝑛 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛 ≤ 3𝑛2 + 2 0 ≤ 𝑐𝑛 𝑐𝑛 ≤ 3𝑛2 + 2 0 ≤ 3𝑛2 − 𝑐𝑛 + 2 𝑐=3 0 ≤ 3𝑛2 − 3𝑛 + 2 0 ≤ 3𝑛 𝑛 − 1 + 2 0≤𝑛−1 1≤𝑛☺ Example 1 Show that 3𝑛2 + 2 = Ω 𝑛 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛 ≤ 3𝑛2 + 2 𝑐=3 𝑛0 = 1 0 ≤ 𝑐𝑛 𝑐𝑛 ≤ 3𝑛2 + 2 0 ≤ 3𝑛2 − 𝑐𝑛 + 2 𝑐=3 0 ≤ 3𝑛2 − 3𝑛 + 2 0 ≤ 3𝑛 𝑛 − 1 + 2 0≤𝑛−1 1≤𝑛☺ Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 There is nothing left to simplify. With 𝑛 being greater than or equal to 0 and 𝑐 being positive, we will always get valid values. ☺ Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 3𝑛3 − 𝑐𝑛3 − 8 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 3𝑛3 − 𝑐𝑛3 − 8 0 ≤ 𝑛3 3 − 𝑐 − 8 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 3𝑛3 − 𝑐𝑛3 − 8 0 ≤ 𝑛3 3 − 𝑐 − 8 𝑐 = 1 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 3𝑛3 − 𝑐𝑛3 − 8 0 ≤ 𝑛3 3 − 1 − 8 𝑐 = 1 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 3𝑛3 − 𝑐𝑛3 − 8 0 ≤ 𝑛3 3 − 1 − 8 𝑐 = 1 0 ≤ 2𝑛3 − 8 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 3𝑛3 − 𝑐𝑛3 − 8 0 ≤ 𝑛3 3 − 1 − 8 𝑐 = 1 0 ≤ 2𝑛3 − 8 8 ≤ 2𝑛3 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 3𝑛3 − 𝑐𝑛3 − 8 0 ≤ 𝑛3 3 − 1 − 8 𝑐 = 1 0 ≤ 2𝑛3 − 8 8 ≤ 2𝑛3 4 ≤ 𝑛3 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 3𝑛3 − 𝑐𝑛3 − 8 0 ≤ 𝑛3 3 − 1 − 8 𝑐 = 1 0 ≤ 2𝑛3 − 8 8 ≤ 2𝑛3 4 ≤ 𝑛3 3 4≤𝑛☺ Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 𝑐=1 3 𝑛0 = 4 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 3𝑛3 − 𝑐𝑛3 − 8 0 ≤ 𝑛3 3 − 1 − 8 𝑐 = 1 0 ≤ 2𝑛3 − 8 8 ≤ 2𝑛3 4 ≤ 𝑛3 3 4≤𝑛☺ Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 There also exists multiple solutions 𝑐=1 3 that validates this proof! As long as 𝑛0 = 4 we choose a valid positive 𝑐 value 0 ≤ 𝑐𝑛3 and obtain the valid range, the 𝑐𝑛3 ≤ 3𝑛3 − 8 notation still stands! Let’s look 0 ≤at3𝑛3 − 𝑐𝑛3 − 8 another one! 0 ≤ 𝑛3 3 − 1 − 8 𝑐 = 1 0 ≤ 2𝑛3 − 8 8 ≤ 2𝑛3 4 ≤ 𝑛3 3 4≤𝑛☺  Instead of choosing 𝑐 = 1, lets choose 𝑐 = 2 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 3𝑛3 − 𝑐𝑛3 − 8 0 ≤ 𝑛3 3 − 𝑐 − 8 𝑐 = 1  Instead of choosing 𝑐 = 1, lets choose 𝑐 = 2 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 3𝑛3 − 𝑐𝑛3 − 8 0 ≤ 𝑛3 3 − 𝑐 − 8 𝑐 = 2  Instead of choosing 𝑐 = 1, lets choose 𝑐 = 2 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 3𝑛3 − 𝑐𝑛3 − 8 0 ≤ 𝑛3 3 − 𝑐 − 8 𝑐 = 2 0 ≤ 𝑛3 3 − 2 − 8  Instead of choosing 𝑐 = 1, lets choose 𝑐 = 2 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 3𝑛3 − 𝑐𝑛3 − 8 0 ≤ 𝑛3 3 − 𝑐 − 8 𝑐 = 2 0 ≤ 𝑛3 3 − 2 − 8 0 ≤ 𝑛3 − 8  Instead of choosing 𝑐 = 1, lets choose 𝑐 = 2 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 3𝑛3 − 𝑐𝑛3 − 8 0 ≤ 𝑛3 3 − 𝑐 − 8 𝑐 = 2 0 ≤ 𝑛3 3 − 2 − 8 0 ≤ 𝑛3 − 8 8 ≤ 𝑛3  Instead of choosing 𝑐 = 1, lets choose 𝑐 = 2 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 3𝑛3 − 𝑐𝑛3 − 8 0 ≤ 𝑛3 3 − 𝑐 − 8 𝑐 = 2 0 ≤ 𝑛3 3 − 2 − 8 0 ≤ 𝑛3 − 8 8 ≤ 𝑛3 2≤𝑛☺  Instead of choosing 𝑐 = 1, lets choose 𝑐 = 2 Example 2 Show that 3𝑛3 − 8 = Ω 𝑛3 𝑐, 𝑛0 = ? 0 ≤ 𝑐𝑛3 ≤ 3𝑛3 − 8 𝑐=2 𝑛0 = 2 0 ≤ 𝑐𝑛3 𝑐𝑛3 ≤ 3𝑛3 − 8 0 ≤ 3𝑛3 − 𝑐𝑛3 − 8 0 ≤ 𝑛3 3 − 𝑐 − 8 𝑐 = 2 0 ≤ 𝑛3 3 − 2 − 8 0 ≤ 𝑛3 − 8 8 ≤ 𝑛3 2≤𝑛☺ Θ-Notation (big-Theta) We use Θ -notation to give a tight bound (asymptotic tight bound) on a function, to within a constant factors. Formal Definition: Θ 𝑔 𝑛 = ሼ𝑇 𝑛 : there exist positive constants 𝑐1 ሺ𝑐1 > 0ሻ, 𝑐2 𝑐2 > 0 and 𝑛0 ≥ 0 such that 0 ≤ 𝑐1 𝑓 𝑛 ≤ 𝑇 𝑛 ≤ 𝑐2 𝑓 𝑛 for all 𝑛 ≥ 𝑛0 ሽ Utilized when f(n) and g(n) have the same order of growth Theorem 𝑇 𝑛 =𝑂 𝑓 𝑛 𝑇 𝑛 = Θ 𝑓 𝑛 𝑖𝑓𝑓 ൝ 𝑇 𝑛 =Ω 𝑓 𝑛 Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 This part of the inequality is already validated with the assumption of 𝑐1 > 0 and 𝑛 ≥ 0. This will always hold true for all valid values. Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 𝑐1 = 7 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 𝑐1 = 7 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 0 ≤ 𝑛2 8 − 7 − 6𝑛 + 3 Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 𝑐1 = 7 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 0 ≤ 𝑛2 − 6𝑛 + 3 Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 𝑐1 = 7 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 0 ≤ 𝑛2 − 6𝑛 + 3 0≤𝑛 𝑛−6 +3 Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 𝑐1 = 7 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 0 ≤ 𝑛2 − 6𝑛 + 3 0≤𝑛 𝑛−6 +3 0≤𝑛−6 Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 𝑐1 = 7 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 0 ≤ 𝑛2 − 6𝑛 + 3 0≤𝑛 𝑛−6 +3 0≤𝑛−6 6≤𝑛☺ Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 𝑐1 = 7 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 0 ≤ 𝑛2 − 6𝑛 + 3 0≤𝑛 𝑛−6 +3 0≤𝑛−6 6≤𝑛☺ Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 0 ≤ 𝑐2 𝑛2 − 8𝑛2 + 6𝑛 − 3 𝑐1 = 7 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 0 ≤ 𝑛2 − 6𝑛 + 3 0≤𝑛 𝑛−6 +3 0≤𝑛−6 6≤𝑛☺ Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 0 ≤ 𝑐2 𝑛2 − 8𝑛2 + 6𝑛 − 3 𝑐1 = 7 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 0 ≤ 𝑛2 𝑐2 − 8 + 6𝑛 − 3 0 ≤ 𝑛2 − 6𝑛 + 3 0≤𝑛 𝑛−6 +3 0≤𝑛−6 6≤𝑛☺ Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 0 ≤ 𝑐2 𝑛2 − 8𝑛2 + 6𝑛 − 3 𝑐1 = 7 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 0 ≤ 𝑛2 𝑐2 − 8 + 6𝑛 − 3 𝑐2 = 8 0 ≤ 𝑛2 − 6𝑛 + 3 0≤𝑛 𝑛−6 +3 0≤𝑛−6 6≤𝑛☺ Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 0 ≤ 𝑐2 𝑛2 − 8𝑛2 + 6𝑛 − 3 𝑐1 = 7 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 0 ≤ 𝑛2 𝑐2 − 8 + 6𝑛 − 3 𝑐2 = 8 0≤ 𝑛2 − 6𝑛 + 3 0 ≤ 𝑛2 8 − 8 + 6𝑛 − 3 0≤𝑛 𝑛−6 +3 0≤𝑛−6 6≤𝑛☺ Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 0 ≤ 𝑐2 𝑛2 − 8𝑛2 + 6𝑛 − 3 𝑐1 = 7 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 0 ≤ 𝑛2 𝑐2 − 8 + 6𝑛 − 3 𝑐2 = 8 0≤ 𝑛2 − 6𝑛 + 3 0 ≤ 𝑛2 8 − 8 + 6𝑛 − 3 0≤𝑛 𝑛−6 +3 0 ≤ 6𝑛 − 3 0≤𝑛−6 6≤𝑛☺ Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 0 ≤ 𝑐2 𝑛2 − 8𝑛2 + 6𝑛 − 3 𝑐1 = 7 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 0 ≤ 𝑛2 𝑐2 − 8 + 6𝑛 − 3 𝑐2 = 8 0≤ 𝑛2 − 6𝑛 + 3 0 ≤ 𝑛2 8 − 8 + 6𝑛 − 3 0≤𝑛 𝑛−6 +3 0 ≤ 6𝑛 − 3 0≤𝑛−6 3 ≤ 6𝑛 6≤𝑛☺ Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 0 ≤ 𝑐2 𝑛2 − 8𝑛2 + 6𝑛 − 3 𝑐1 = 7 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 0 ≤ 𝑛2 𝑐2 − 8 + 6𝑛 − 3 𝑐2 = 8 0≤ 𝑛2 − 6𝑛 + 3 0 ≤ 𝑛2 8 − 8 + 6𝑛 − 3 0≤𝑛 𝑛−6 +3 0 ≤ 6𝑛 − 3 0≤𝑛−6 3 ≤ 6𝑛 3 6≤𝑛☺ ≤𝑛 6 Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 0 ≤ 𝑐2 𝑛2 − 8𝑛2 + 6𝑛 − 3 𝑐1 = 7 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 0 ≤ 𝑛2 𝑐2 − 8 + 6𝑛 − 3 𝑐2 = 8 0≤ 𝑛2 − 6𝑛 + 3 0 ≤ 𝑛2 8 − 8 + 6𝑛 − 3 0≤𝑛 𝑛−6 +3 0 ≤ 6𝑛 − 3 0≤𝑛−6 3 ≤ 6𝑛 1 6≤𝑛☺ ≤𝑛☺ 2 Example 1 Show that 8𝑛2 − 6𝑛 + 3 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑐1 = 7 𝑐2 = 8 𝑐1 𝑛2 ≤ 8𝑛2 − 6𝑛 + 3 8𝑛2 − 6𝑛 + 3 ≤ 𝑐2 𝑛2 𝑛0 = 6 0 ≤ 8𝑛2 − 𝑐1 𝑛2 − 6𝑛 + 3 0 ≤ 𝑐2 𝑛2 − 8𝑛2 + 6𝑛 − 3 𝑐1 = 7 0 ≤ 𝑛2 8 − 𝑐1 − 6𝑛 + 3 0 ≤ 𝑛2 𝑐2 − 8 + 6𝑛 − 3 𝑐2 = 8 0≤ 𝑛2 − 6𝑛 + 3 0 ≤ 𝑛2 8 − 8 + 6𝑛 − 3 0≤𝑛 𝑛−6 +3 0 ≤ 6𝑛 − 3 0≤𝑛−6 3 ≤ 6𝑛 1 6≤𝑛☺ ≤𝑛☺ 2 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 This part of the inequality is already validated with the assumption of 𝑐1 > 0 and 𝑛 ≥ 0. This will always hold true for all valid values. Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 0 ≤ 9𝑛2 − 𝑐1 𝑛2 + 3𝑛 − 2 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 0 ≤ 9𝑛2 − 𝑐1 𝑛2 + 3𝑛 − 2 𝑐1 = 9 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 0 ≤ 9𝑛2 − 𝑐1 𝑛2 + 3𝑛 − 2 𝑐1 = 9 0 ≤ 9𝑛2 − 9𝑛2 + 3𝑛 − 2 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 0 ≤ 9𝑛2 − 𝑐1 𝑛2 + 3𝑛 − 2 𝑐1 = 9 0 ≤ 9𝑛2 − 9𝑛2 + 3𝑛 − 2 0 ≤ 3𝑛 − 2 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 0 ≤ 9𝑛2 − 𝑐1 𝑛2 + 3𝑛 − 2 𝑐1 = 9 0 ≤ 9𝑛2 − 9𝑛2 + 3𝑛 − 2 0 ≤ 3𝑛 − 2 2 ≤ 3𝑛 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 0 ≤ 9𝑛2 − 𝑐1 𝑛2 + 3𝑛 − 2 𝑐1 = 9 0 ≤ 9𝑛2 − 9𝑛2 + 3𝑛 − 2 0 ≤ 3𝑛 − 2 2 ≤ 3𝑛 2 ≤𝑛☺ 3 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 0 ≤ 9𝑛2 − 𝑐1 𝑛2 + 3𝑛 − 2 𝑐1 = 9 0 ≤ 9𝑛2 − 9𝑛2 + 3𝑛 − 2 0 ≤ 3𝑛 − 2 2 ≤ 3𝑛 2 ≤𝑛☺ 3 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 0 ≤ 9𝑛2 − 𝑐1 𝑛2 + 3𝑛 − 2 𝑐1 = 9 0 ≤ 𝑐2 𝑛2 − 9𝑛2 − 3𝑛 + 2 0 ≤ 9𝑛2 − 9𝑛2 + 3𝑛 − 2 0 ≤ 3𝑛 − 2 2 ≤ 3𝑛 2 ≤𝑛☺ 3 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 0 ≤ 9𝑛2 − 𝑐1 𝑛2 + 3𝑛 − 2 𝑐1 = 9 0 ≤ 𝑐2 𝑛2 − 9𝑛2 − 3𝑛 + 2 𝑐2 = 10 0 ≤ 9𝑛2 − 9𝑛2 + 3𝑛 − 2 0 ≤ 3𝑛 − 2 2 ≤ 3𝑛 2 ≤𝑛☺ 3 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 0 ≤ 9𝑛2 − 𝑐1 𝑛2 + 3𝑛 − 2 𝑐1 = 9 0 ≤ 𝑐2 𝑛2 − 9𝑛2 − 3𝑛 + 2 𝑐2 = 10 0 ≤ 9𝑛2 − 9𝑛2 + 3𝑛 − 2 0 ≤ 10𝑛2 − 9𝑛2 − 3𝑛 + 2 0 ≤ 3𝑛 − 2 2 ≤ 3𝑛 2 ≤𝑛☺ 3 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 0 ≤ 9𝑛2 − 𝑐1 𝑛2 + 3𝑛 − 2 𝑐1 = 9 0 ≤ 𝑐2 𝑛2 − 9𝑛2 − 3𝑛 + 2 𝑐2 = 10 0 ≤ 9𝑛2 − 9𝑛2 + 3𝑛 − 2 0 ≤ 10𝑛2 − 9𝑛2 − 3𝑛 + 2 0 ≤ 3𝑛 − 2 0 ≤ 𝑛2 − 3𝑛 + 2 2 ≤ 3𝑛 2 ≤𝑛☺ 3 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 0 ≤ 9𝑛2 − 𝑐1 𝑛2 + 3𝑛 − 2 𝑐1 = 9 0 ≤ 𝑐2 𝑛2 − 9𝑛2 − 3𝑛 + 2 𝑐2 = 10 0 ≤ 9𝑛2 − 9𝑛2 + 3𝑛 − 2 0 ≤ 10𝑛2 − 9𝑛2 − 3𝑛 + 2 0 ≤ 3𝑛 − 2 0 ≤ 𝑛2 − 3𝑛 + 2 2 ≤ 3𝑛 0≤𝑛 𝑛−3 +2 2 ≤𝑛☺ 3 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 0 ≤ 9𝑛2 − 𝑐1 𝑛2 + 3𝑛 − 2 𝑐1 = 9 0 ≤ 𝑐2 𝑛2 − 9𝑛2 − 3𝑛 + 2 𝑐2 = 10 0 ≤ 9𝑛2 − 9𝑛2 + 3𝑛 − 2 0 ≤ 10𝑛2 − 9𝑛2 − 3𝑛 + 2 0 ≤ 3𝑛 − 2 0 ≤ 𝑛2 − 3𝑛 + 2 2 ≤ 3𝑛 0≤𝑛 𝑛−3 +2 2 ≤𝑛☺ 0≤𝑛−3 3 Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 0 ≤ 9𝑛2 − 𝑐1 𝑛2 + 3𝑛 − 2 𝑐1 = 9 0 ≤ 𝑐2 𝑛2 − 9𝑛2 − 3𝑛 + 2 𝑐2 = 10 0 ≤ 9𝑛2 − 9𝑛2 + 3𝑛 − 2 0 ≤ 10𝑛2 − 9𝑛2 − 3𝑛 + 2 0 ≤ 3𝑛 − 2 0 ≤ 𝑛2 − 3𝑛 + 2 2 ≤ 3𝑛 0≤𝑛 𝑛−3 +2 2 ≤𝑛☺ 0≤𝑛−3 3 3≤𝑛☺ Example 2 Show that 9𝑛2 + 3𝑛 − 2 = Θ 𝑛2 𝑐1 , 𝑐2 , 𝑛0 = ? 0 ≤ 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑐1 = 9 𝑐2 = 10 𝑐1 𝑛2 ≤ 9𝑛2 + 3𝑛 − 2 9𝑛2 + 3𝑛 − 2 ≤ 𝑐2 𝑛2 𝑛0 = 3 0 ≤ 9𝑛2 − 𝑐 𝑛2 + 3𝑛 − 2 𝑐 = 9 0 ≤ 𝑐2 𝑛2 − 9𝑛2 − 3𝑛 + 2 𝑐2 = 10 1 1 0 ≤ 9𝑛2 − 9𝑛2 + 3𝑛 − 2 0 ≤ 10𝑛2 − 9𝑛2 − 3𝑛 + 2 0 ≤ 3𝑛 − 2 0 ≤ 𝑛2 − 3𝑛 + 2 2 ≤ 3𝑛 0≤𝑛 𝑛−3 +2 2 ≤𝑛☺ 0≤𝑛−3 3 3≤𝑛☺  Interesting Analogies The 3 asymptomatic notation can simply show these analogies 𝑇 𝑛 =𝑂 𝑓 𝑛 𝑓 𝑛 ≤𝑔 𝑛 𝑇 𝑛 =Ω 𝑓 𝑛 𝑓 𝑛 ≥𝑔 𝑛 𝑇 𝑛 =Θ 𝑓 𝑛 𝑓 𝑛 =𝑔 𝑛 7𝑛2 − 2𝑛 + 10 = 𝑂 𝑛3 ☺ 7𝑛2 − 2𝑛 + 10 = Ω 𝑛3  7𝑛2 − 2𝑛 + 10 = Θ 𝑛3  7𝑛2 − 2𝑛 + 10 = 𝑂 𝑛2 ☺ 7𝑛2 − 2𝑛 + 10 = Ω 𝑛2 ☺ 7𝑛2 − 2𝑛 + 10 = Θ 𝑛2 ☺ 7𝑛2 − 2𝑛 + 10 = 𝑂 𝑛  7𝑛2 − 2𝑛 + 10 = Ω 𝑛 ☺ 7𝑛2 − 2𝑛 + 10 = Θ 𝑛  Exponential Identities Review For all real 𝑎 > 0, 𝑚, and 𝑛, we have the following identities: 𝑎0 = 1 𝑎1 = 𝑎 1 𝑎−1 = 𝑎 𝑎𝑚 𝑛 = 𝑎𝑚𝑛 𝑎𝑚 𝑎𝑛 = 𝑎𝑚+𝑛 Growth of Functions Function Name c Constant 𝑙𝑜𝑔2 𝑛 Logarithmic 𝑛 Linear 𝑛𝑙𝑜𝑔2 𝑛 Linearithmic 𝑛2 Quadratic 𝑛3 Cubic 2𝑛 Exponential 𝑛! Factorial Example Arrange the following functions in ascending order of growth rate. That is if 𝑔 𝑥 follows 𝑓 𝑥 , then it should be the case 𝑓 𝑥 = 𝑂 𝑔 𝑥. 𝑓1 = 2𝑥 4 4 𝑓2 = 𝑥4 𝑓3 = log 78𝑥 𝑓4 = 4𝑥 5 1 2𝑥 𝑓5 = 4 Example Arrange the following functions in ascending order of growth rate. That is if 𝑔 𝑥 follows 𝑓 𝑥 , then it should be the case 𝑓 𝑥 = 𝑂 𝑔 𝑥. 𝑓1 = 2𝑥 4 4 𝑓2 = 𝑥4 𝑓3 = log 78𝑥 𝑓5 𝑓4 = 4𝑥 5 1 2𝑥 𝑓5 = 4 Example Arrange the following functions in ascending order of growth rate. That is if 𝑔 𝑥 follows 𝑓 𝑥 , then it should be the case 𝑓 𝑥 = 𝑂 𝑔 𝑥. 𝑓1 = 2𝑥 4 4 𝑓2 = 𝑥4 𝑓3 = log 78𝑥 𝑓5 , 𝑓3 𝑓4 = 4𝑥 5 1 2𝑥 𝑓5 = 4 Example Arrange the following functions in ascending order of growth rate. That is if 𝑔 𝑥 follows 𝑓 𝑥 , then it should be the case 𝑓 𝑥 = 𝑂 𝑔 𝑥. 𝑓1 = 2𝑥 4 4 𝑓2 = 𝑥4 𝑓3 = log 78𝑥 𝑓5 , 𝑓3 , 𝑓2 𝑓4 = 4𝑥 5 1 2𝑥 𝑓5 = 4 Example Arrange the following functions in ascending order of growth rate. That is if 𝑔 𝑥 follows 𝑓 𝑥 , then it should be the case 𝑓 𝑥 = 𝑂 𝑔 𝑥. 𝑓1 = 2𝑥 4 4 𝑓2 = 𝑥4 𝑓3 = log 78𝑥 𝑓5 , 𝑓3 , 𝑓2 , 𝑓1 𝑓4 = 4𝑥 5 1 2𝑥 𝑓5 = 4 Example Arrange the following functions in ascending order of growth rate. That is if 𝑔 𝑥 follows 𝑓 𝑥 , then it should be the case 𝑓 𝑥 = 𝑂 𝑔 𝑥. 𝑓1 = 2𝑥 4 4 𝑓2 = 𝑥4 𝑓3 = log 78𝑥 𝑓5 , 𝑓3 , 𝑓2 , 𝑓1 , 𝑓4 𝑓4 = 4𝑥 5 1 2𝑥 𝑓5 = 4  B-Trees COP 3503 Spring 2025 Department of Computer Science University of Central Florida Dr. Steinberg Reference The following presentation is referenced from the Cormen Introduction to Algorithms 3rd edition Textbook. Introduction Binary Search Trees – Trees where a node has only at most two children. The value of the left node is smaller than the parent node value and the right node value is larger than the parent node. Examples: 10 1 5 13 2 4 15 3 4 Introduction Binary Search Trees – Trees where a node has only at most two children. The value of the left node is smaller than the parent node value and the right node value is larger than the parent node. Examples: What is wrong with 10 1 the 5 13 right Binary2 4 search 15 tree? 3 4 B-Trees Balanced Search Trees One con with a Binary Search Tree (BST) is that we can potentially have our algorithms run in linear time rather than height level time. B-Trees nodes have many children (few to even thousands!) This data structure is primarily used in disks and other direct-access secondary storage devices. Database systems use B-Trees or even variants. The height of a B-tree is 𝑂(lg 𝑛)  B-Tree Sample In this sample, the keys are integers Each node has x.n keys and x.n + 1children How does a search work for key 126? T.root 123 36 110 136 160 198 19 25 56 98 115 119 120 126 130 141 157 174 188 236 380 Data Structures on Secondary Storage Primary memory (main memory) consists of silicon memory chips. Secondary storage consists of magnetic storage Tapes Disks Disks are cheaper and have higher capacity than the main memory. Disks are slower than main memory due to motion mechanical components. Disk Drive The average access time for the disk ranges from 8 to 11 milliseconds. The average access time in main memory is about 50 nanoseconds! Information on a disk is divided into pages which range from 211 − 214 bytes. Each disk reads and/or writes on a single or multiple pages. B-Tree Applications The Whole B-Trees does not fit in the main memory!!! Operating Systems copies the pages from the disks into main memory. After performing tasks, the operating system writes back to the respective pages that were modified. x = a pointer to some object DISK-WRITE(x) operations that access and/or modify attributes of x DISK-READ(x) other operations that access but do not modify attributes of x B-Tree Example Branch Factor = 1001 Height = 2 1000 1001 1000 1000 1001 1001 1000 … 1000 B-Trees often have branching factors ranging from 50 -2000 Root node is permanently in main memory in order to find any key with at most two disk accesses. B-Tree Example Branch Factor = 1001 Height = 2 Think 1000 About it… Imagine 1000 trying 1001 1000 to store … this in RAM!! 1001 1001 1000 1000 CRAZY!!!!!!!!!! B-Trees often have branching factors ranging from 50 -2000 Root node is permanently in main memory in order to find any key with at most two disk accesses. The Official B-Tree Definition A B-Tree is a rooted tree (where T.root is the root) with the following properties: 1. Every node x has the following attributes a) x.n is the number of keys currently stored in x b) The keys 𝑥. 𝑘𝑒𝑦1 , 𝑥. 𝑘𝑒𝑦2 , … , 𝑥. 𝑘𝑒𝑦𝑥.𝑛 such that 𝑥. 𝑘𝑒𝑦1 ≤ 𝑥. 𝑘𝑒𝑦2 ≤ … ≤ 𝑥. 𝑘𝑒𝑦𝑥.𝑛 c) x.leaf – a Boolean value which is true if x is a leaf and false if x is an internal node 2. Each internal node x has 𝑥. 𝑛 + 1 pointers 𝑥.𝑐1 , 𝑥.𝑐2 , … , 𝑥.𝑐𝑥.𝑛+1 to its children. If x is a leaf then the pointers are undefined. 3. If 𝑘𝑖 is any key stored in the subtree with root 𝑥. 𝑐𝑖 then: 𝑘1 ≤ 𝑥. 𝑘𝑒𝑦1 ≤ 𝑘2 ≤ 𝑥. 𝑘𝑒𝑦2 ≤ … ≤ 𝑥. 𝑘𝑒𝑦𝑥.𝑛 ≤ 𝑘𝑥.𝑛+1 The official B-Tree Definition Continued All leaves have the same depth, which is the tree high ℎ. The B-Tree has a minimum degree t (where t is an integer t >= 2): Every node other than the root must have >= t – 1 keys and >= t children; if B- tree is nonempty, then the root has at least one key Every node has ≤ 2𝑡 – 1 keys and ≤ 2𝑡 children A node is considered full if it has 2t – 1 keys inserted. Interesting Theorem About Height in B-Trees Theorem: if 𝑛 ≥ 1, then for any n-key B-tree T of height h and minimum degree t, 𝑛+1 ℎ ≤ log 𝑡 2ℎ 𝑛 ≥ 1 + 𝑡 − 1 ෍ 2𝑡 𝑖−1 𝑖=1 ℎ = 1 + 2 𝑡 − 1 ෍ 𝑡 𝑖−1 𝑖=1 𝑡ℎ − 1 =1+2 𝑡−1 = 2𝑡 ℎ − 1 𝑡−1 𝑛 + 1 𝑡ℎ ≤ 2 𝑛+1 ℎ ≤ log 𝑡 2 ℎ = 𝑂 log 𝑛 Theorem cont. ℎ 𝑛 ≥ 1 + 𝑡 − 1 ෍ 2𝑡 𝑖−1 𝑖=1 ℎ = 1 + 2 𝑡 − 1 ෍ 𝑡 𝑖−1 𝑖=1 𝑡ℎ − 1 =1+2 𝑡−1 = 2𝑡 ℎ − 1 𝑡−1 𝑛 + 1 𝑡ℎ ≤ 2 𝑛+1 ℎ ≤ log 𝑡 2 ℎ = 𝑂 log 𝑛  # of depth nodes 1 0 1 𝑡−1 𝑡−1 1 2 𝑡 𝑡 𝑡−1 𝑡−1 𝑡−1 𝑡−1 2 2𝑡 𝑡 𝑡 𝑡 𝑡 𝑡−1 … 𝑡−1 𝑡−1 … 𝑡−1 𝑡−1 … 𝑡−1 𝑡−1 … 𝑡−1 3 2𝑡 2 Operations We Will Observe for B-Trees B-Tree-Search B-Tree-Create B-Tree-Insert B-Tree-Delete B-Tree Search B-Tree-Search(x, k) i=1 while 𝑖 ≤ 𝑥. 𝑛 and 𝑘 > 𝑥 i=i+1 if 𝑖 ≤ 𝑥. 𝑛 and k == 𝑥. 𝑘𝑒𝑦𝑖 return (x, i) else if x.leaf == True return NULL else DISK-READ(𝑥. 𝑐𝑖 ) return B-Tree-Search(𝑥. 𝑐𝑖 , 𝑘) RT: 𝑂 𝑡𝑙𝑜𝑔𝑡 𝑛 B-Tree-Create Creating an empty tree with root node B-Tree-Create(T) x = Allocate-Node() x.leaf = True x.n = 0 Disk-Write(x) T.root = x B-Tree Insert Operations The insert operation has 3 functions/methods we need to understand B-Tree-Split-Child(x,i) B-Tree-Insert(T,k) B-Tree-Insert-Nonfull(x,k) Insert Operation and Overall Goal Search for a leaf where to put new key Inserting into an existing leaf node Cannot create a new leaf If the leaf node is full, then split around the median key The overall goal is to insert they key while maintaining B-Tree rules. As the algorithms traverses down the tree, it splits each full node along the way, including the leaf. Splitting a Node 136 160 198 200 213 Splitting a Node 136 160 198 200 213 SPLIT Splitting a Node 198 136 160 198 200 213 SPLIT 136 160 200 213  Splitting a Node 198 136 160 198 200 213 SPLIT 136 160 200 213 198 136 146 153 155 160 200 213  Splitting a Node 198 136 160 198 200 213 SPLIT 136 160 200 213 198 SPLIT 136 146 153 155 160 200 213  Splitting a Node 198 136 160 198 200 213 SPLIT 136 160 200 213 153 198 198 SPLIT 136 146 155 160 200 213 136 146 153 155 160 200 213 B-Tree-Insert() t=4 range of keys 3-7 200 136 160 198 200 213 252 311 SPLIT 136 160 198 213 252 311 If root node is full, then split the root and new node will become the root RT for Insert 𝑂(𝑡ℎ) = 𝑂 𝑡𝑙𝑜𝑔𝑡 𝑛 B-Tree-Delete() Important things to remember! When a key is removed, we must rearrange the node’s children! Any node (EXCEPT FOR THE ROOT) cannot have fewer than t -1 keys The algorithm deletes a key k from the subtree rooted at x Something to consider: When delete is called on a node, we should guarantee that the number of keys in x is greater than or equal to t. The overall objective is to remove a key while maintaining the B-tree properties. There are 3 rules to consider when deleting from the B-Tree  Rule 1 If the key k is part of a leaf node x, then just delete the key. t=2 Delete 120 T.root 123 36 48 110 136 160 198 19 25 40 45 56 98 115 119 120 126 130 141 157 174 188 236 380  Rule 1 If the key k is part of a leaf node x, then just delete the key. t=2 Delete 120 T.root 123 36 48 110 136 160 198 19 25 40 45 56 98 115 119 120 126 130 141 157 174 188 236 380  Rule 1 If the key k is part of a leaf node x, then just delete the key. t=2 Delete 120 T.root 123 36 48 110 136 160 198 19 25 40 45 56 98 115 119 126 130 141 157 174 188 236 380  Rule 2a If the key k belongs to an internal node x. If the child y that precedes k in a node x has at least t keys, then find the predecessor k’ of k in the subtree rooted at y. Recursively delete k’ and replace k by k’ in x. t=2 T.root Delete 48 123 36 48 110 136 160 198 19 25 40 45 56 98 115 119 126 130 141 157 174 188 236 380  Rule 2a If the key k belongs to an internal node x. If the child y that precedes k in a node x has at least t keys, then find the predecessor k’ of k in the subtree rooted at y. Recursively delete k’ and replace k by k’ in x. t=2 T.root Delete 48 123 x 36 48 110 136 160 198 19 25 40 45 56 98 115 119 126 130 141 157 174 188 236 380  Rule 2a If the key k belongs to an internal node x. If the child y that precedes k in a node x has at least t keys, then find the predecessor k’ of k in the subtree rooted at y. Recursively delete k’ and replace k by k’ in x. t=2 T.root Delete 48 123 x 36 48 110 136 160 198 y 19 25 40 45 56 98 115 119 126 130 141 157 174 188 236 380  Rule 2a If the key k belongs to an internal node x. If the child y that precedes k in a node x has at least t keys, then find the predecessor k’ of k in the subtree rooted at y. Recursively delete k’ and replace k by k’ in x. t=2 T.root Delete 48 123 36 45 110 136 160 198 19 25 40 56 98 115 119 126 130 141 157 174 188 236 380  Rule 2b If the key k belongs to an internal node. If y has fewer than t keys, then, symmetrically, examine the child z that follows k in node x. If z has at least t keys, then find the successor k’ of k in the subtree rooted at z. Recursively delete k’ and replace k by k’ in x. t=2 Delete 45 T.root 123 36 45 110 136 160 198 19 25 40 56 98 115 119 126 130 141 157 174 188 236 380  Rule 2b If the key k belongs to an internal node. If y has fewer than t keys, then, symmetrically, examine the child z that follows k in node x. If z has at least t keys, then find the successor k’ of k in the subtree rooted at z. Recursively delete k’ and replace k by k’ in x. t=2 Delete 45 T.root 123 x 36 45 110 136 160 198 19 25 40 56 98 115 119 126 130 141 157 174 188 236 380  Rule 2b If the key k belongs to an internal node. If y has fewer than t keys, then, symmetrically, examine the child z that follows k in node x. If z has at least t keys, then find the successor k’ of k in the subtree rooted at z. Recursively delete k’ and replace k by k’ in x. t=2 Delete 45 T.root 123 x 36 45 110 136 160 198 y 19 25 40 56 98 115 119 126 130 141 157 174 188 236 380  Rule 2b If the key k belongs to an internal node. If y has fewer than t keys, then, symmetrically, examine the child z that follows k in node x. If z has at least t keys, then find the successor k’ of k in the subtree rooted at z. Recursively delete k’ and replace k by k’ in x. t=2 Delete 45 T.root 123 x 36 45 110 136 160 198 z 19 25 40 56 98 115 119 126 130 141 157 174 188 236 380  Rule 2b If the key k belongs to an internal node. If y has fewer than t keys, then, symmetrically, examine the child z that follows k in node x. If z has at least t keys, then find the successor k’ of k in the subtree rooted at z. Recursively delete k’ and replace k by k’ in x. t=2 Delete 45 T.root 123 36 56 110 136 160 198 19 25 40 98 115 119 126 130 141 157 174 188 236 380  Rule 2c If the key k belongs to an internal node x. Otherwise, if both y and z have only t – 1 keys, merge k and all of z into y, so that x loses both k and the pointer to z, and y now contains 2t -1 keys. Then free z and recursively delete k from y. t=2 T.root 123 Delete 56 36 56 110 136 160 198 19 25 40 98 115 119 126 130 141 157 174 188 236 380  Rule 2c If the key k belongs to an internal node x. Otherwise, if both y and z have only t – 1 keys, merge k and all of z into y, so that x loses both k and the pointer to z, and y now contains 2t -1 keys. Then free z and recursively delete k from y. t=2 T.root 123 Delete 56 x 36 56 110 136 160 198 19 25 40 98 115 119 126 130 141 157 174 188 236 380  Rule 2c If the key k belongs to an internal node x. Otherwise, if both y and z have only t – 1 keys, merge k and all of z into y, so that x loses both k and the pointer to z, and y now contains 2t -1 keys. Then free z and recursively delete k from y. t=2 T.root 123 Delete 56 x 36 56 110 136 160 198 y z 19 25 40 98 115 119 126 130 141 157 174 188 236 380 Both Nodes have t – 1 keys  Rule 2c If the key k belongs to an internal node x. Otherwise, if both y and z have only t – 1 keys, merge k and all of z into y, so that x loses both k and the pointer to z, and y now contains 2t -1 keys. Then free z and recursively delete k from y. t=2 T.root 123 Delete 56 36 110 136 160 198 y 19 25 40 56 98 115 119 126 130 141 157 174 188 236 380 Pull Down and Merge  Rule 2c If the key k belongs to an internal node x. Otherwise, if both y and z have only t – 1 keys, merge k and all of z into y, so that x loses both k and the pointer to z, and y now contains 2t -1 keys. Then free z and recursively delete k from y. t=2 T.root 123 Delete 56 36 110 136 160 198 19 25 40 98 115 119 126 130 141 157 174 188 236 380 Apply Rule 1  Rule 3a If the key k is not part of the internal node x, take 𝑥. 𝑐𝑖 the root of the subtree that must contain k (if k is in the tree). If 𝑥. 𝑐𝑖 has only t-1 keys, then use 3a or 3b to guarantee we descend to a node with greater than or equal to t keys. If 𝑥. 𝑐𝑖 has an immediate sibling with greater than or equal to t keys, then give 𝑥. 𝑐𝑖 an extra key by: Moving a key from x to 𝑥. 𝑐𝑖 Moving a key from 𝑥. 𝑐𝑖 ’s immediate left or right sibling up x Moving the appropriate child pointer from the sibling into 𝑥. 𝑐𝑖 T.root 123 t=2 Delete 36 36 136 160 198 19 25 40 98  Rule 3a If the key k is not part of the internal node x, take 𝑥. 𝑐𝑖 the root of the subtree that must contain k (if k is in the tree). If 𝑥. 𝑐𝑖 has only t-1 keys, then use 3a or 3b to guarantee we descend to a node with greater than or equal to t keys. If 𝑥. 𝑐𝑖 has an immediate sibling with greater than or equal to t keys, then give 𝑥. 𝑐𝑖 an extra key by: Moving a key from x to 𝑥. 𝑐𝑖 Moving a key from 𝑥. 𝑐𝑖 ’s immediate left or right sibling up x Key is not in Moving the appropriate child pointer from the sibling into 𝑥. 𝑐𝑖 highlighted node… T.root 123 x take root of subtree t=2 that must contain k Delete 36 36 136 160 198 19 25 40 98  Rule 3a If the key k is not part of the internal node x, take 𝑥. 𝑐𝑖 the root of the subtree that must contain k (if k is in the tree). If 𝑥. 𝑐𝑖 has only t-1 keys, then use 3a or 3b to guarantee we descend to a node with greater than or equal to t keys. If 𝑥. 𝑐𝑖 has an immediate sibling with greater than or equal to t keys, then give 𝑥. 𝑐𝑖 an extra key by: Moving a key from x to 𝑥. 𝑐𝑖 Moving a key from 𝑥. 𝑐𝑖 ’s immediate left or right sibling up x Moving the appropriate child pointer from the sibling into 𝑥. 𝑐𝑖 x.ci has 𝒕 − 𝟏. Apply Rule 3. T.root 123 x Start with 3A. t=2 Delete 36 36 𝑥. 𝑐𝑖 136 160 198 19 25 40 98  Rule 3a If the key k is not part of the internal node x, take 𝑥. 𝑐𝑖 the root of the subtree that must contain k (if k is in the tree). If 𝑥. 𝑐𝑖 has only t-1 keys, then use 3a or 3b to guarantee we descend to a node with greater than or equal to t keys. If 𝑥. 𝑐𝑖 has an immediate sibling with greater than or equal to t keys, then give 𝑥. 𝑐𝑖 an extra key by: Moving a key from x to 𝑥. 𝑐𝑖 Moving a key from 𝑥. 𝑐𝑖 ’s immediate left or right sibling up x Moving the appropriate child pointer from the sibling into 𝑥. 𝑐𝑖 Start with left sibling. However there is no left sibling. Now we T.root x check the right sibling. Here we see 123 that the node has at least t keys. t=2 Delete 36 36 𝑥. 𝑐𝑖 136 160 198 19 25 40 98  Rule 3a If the key k is not part of the internal node x, take 𝑥. 𝑐𝑖 the root of the subtree that must contain k (if k is in the tree). If 𝑥. 𝑐𝑖 has only t-1 keys, then use 3a or 3b to guarantee we descend to a node with greater than or equal to t keys. If 𝑥. 𝑐𝑖 has an immediate sibling with greater than or equal to t keys, then give 𝑥. 𝑐𝑖 an extra key by: Moving a key from x to 𝑥. 𝑐𝑖 Moving a key from 𝑥. 𝑐𝑖 ’s immediate left or right sibling up x Moving the appropriate child pointer from the sibling into 𝑥. 𝑐𝑖 T.root 136 t=2 Delete 36 36 123 𝑥 160 198 19 25 40 98  Rule 3a If the key k is not part of the internal node x, take 𝑥. 𝑐𝑖 the root of the subtree that must contain k (if k is in the tree). If 𝑥. 𝑐𝑖 has only t-1 keys, then use 3a or 3b to guarantee we descend to a node with greater than or equal to t keys. If 𝑥. 𝑐𝑖 has an immediate sibling with greater than or equal to t keys, then give 𝑥. 𝑐𝑖 an extra key by: Moving a key from x to 𝑥. 𝑐𝑖 Moving a key from 𝑥. 𝑐𝑖 ’s immediate left or right sibling up x Moving the appropriate child pointer from the sibling into 𝑥. 𝑐𝑖 T.root 136 t=2 Delete 36 36 123 𝑥 160 198 19 25 40 98 Apply Rule 2A  Rule 3a If the key k is not part of the internal node x, take 𝑥. 𝑐𝑖 the root of the subtree that must contain k (if k is in the tree). If 𝑥. 𝑐𝑖 has only t-1 keys, then use 3a or 3b to guarantee we descend to a node with greater than or equal to t keys. If 𝑥. 𝑐𝑖 has an immediate sibling with greater than or equal to t keys, then give 𝑥. 𝑐𝑖 an extra key by: Moving a key from x to 𝑥. 𝑐𝑖 Moving a key from 𝑥. 𝑐𝑖 ’s immediate left or right sibling up x Moving the appropriate child pointer from the sibling into 𝑥. 𝑐𝑖 T.root 136 t=2 Delete 36 25 123 160 198 19 40 98 Rule 3b If both 𝑥. 𝑐𝑖 ’s immediate sibling have t – 1 keys, merge 𝑥. 𝑐𝑖 with one sibling, which involves moving a key from x down into the new merged node to become the median for that node Delete 25 t=2 T.root 136 25 198 19 40 98 196 210 255 Rule 3b If both 𝑥. 𝑐𝑖 ’s immediate sibling have t – 1 keys, merge 𝑥. 𝑐𝑖 with one sibling, which involves moving a key from x down into the new merged node to become the median for that node Delete 25 Key is not in highlighted t=2 node… take root of subtree T.root x that must contain k 136 25 198 19 40 98 196 210 255 Rule 3b If both 𝑥. 𝑐𝑖 ’s immediate sibling have t – 1 keys, merge 𝑥. 𝑐𝑖 with one sibling, which involves moving a key from x down into the new merged node to become the median for that node Delete 25 x.ci has 𝒕 − 𝟏. Apply Rule 3. Start t=2 with 3A. T.root x 136 25 𝑥. 𝑐𝑖 198 19 40 98 196 210 255 Rule 3b If both 𝑥. 𝑐𝑖 ’s immediate sibling have t – 1 keys, merge 𝑥. 𝑐𝑖 with one sibling, which involves moving a key from x down into the new merged node to become the median for that node Delete 25 3A doesn’t work sadly… BUT we t=2 apply 3B! T.root x 136 25 𝑥. 𝑐𝑖 198 19 40 98 196 210 255 Rule 3b If both 𝑥. 𝑐𝑖 ’s immediate sibling have t – 1 keys, merge 𝑥. 𝑐𝑖 with one sibling, which involves moving a key from x down into the new merged node to become the median for that node Delete 25 t=2 T.root x 25 136 198 19 40 98 196 210 255 Rule 3b If both 𝑥. 𝑐𝑖 ’s immediate sibling have t – 1 keys, merge 𝑥. 𝑐𝑖 with one sibling, which involves moving a key from x down into the new merged node to become the median for that node Delete 25 t=2 T.root x 25 136 198 19 40 98 196 210 255 Apply Rule 2B Rule 3b If both 𝑥. 𝑐𝑖 ’s immediate sibling have t – 1 keys, merge 𝑥. 𝑐𝑖 with one sibling, which involves moving a key from x down into the new merged node to become the median for that node Delete 25 t=2 T.root x 40 136 198 19 98 196 210 255 RT for Delete RT is 𝑂 𝑡ℎ = 𝑂 𝑡𝑙𝑜𝑔𝑡 𝑛 Backtracking COP 3503 Spring 2025 Department of Computer Science University of Central Florida Dr. Steinberg Introduction We just observed Divide and Conquer (DC) in designing an efficient running time algorithm. DC yields the correct results to problems. There can be more than one correct result, however one may be better than the other. In this lecture we will discuss another advanced technique called Backtracking What kind of problems does Backtracking Solve? Combinatorial Problems Puzzles Finding Feasible Solutions Finding the Optimal Solution Quick Review of Tree Terminology Backtracking Uses a Search Tree The Root is the starting state before the search for solutions Nodes on the first level, choices made for the first component of the solution Nodes on the second level, choices for second component of the solution The pattern continues… Each node on the tree is considered a potential solution, if it corresponds to a partially constructed solution that may still lead to a full solution. Leaves in the tree are dead ends or complete solution. The Search Tree Construction If the current node is considered a potential solution, its child is generated by adding the first remaining legitimate option for the next component of a solution The algorithm moves onto the child If the current node is NOT considered a potential solution, then the algorithm “backtracks” to the parent to consider the next potential solution. If no option is possible, then the algorithm backtracks up on more level in the search tree. If the potential solution turns out to be the complete solution, then the algorithm stops (assuming we are searching for one solution). The Big Picture of Backtracking The Big Picture of Backtracking The Big Picture of Backtracking The Big Picture of Backtracking The Big Picture of Backtracking Backtrack The Big Picture of Backtracking Backtrack The Big Picture of Backtracking Still Potential Backtrack The Big Picture of Backtracking Still Potential Backtrack Backtrack The Big Picture of Backtracking No Longer Potential Backtrack Backtrack The Big Picture of Backtracking Backtrack No Longer Potential Backtrack Backtrack The Big Picture of Backtracking Backtrack Backtrack Backtrack The Big Picture of Backtracking Backtrack Backtrack Backtrack The Big Picture of Backtracking Backtrack Backtrack Backtrack The Big Picture of Backtracking Backtrack Backtrack Backtrack The Big Picture of Backtracking Backtrack Backtrack Backtrack A Solution Has Been Found Based on observation of Backtracking what kind of problems can we apply this technique too? From the description, are there limitations? Let’s Observe the Classic N-Queens Problem Problem Definition The n-queens problem is to place n queens on an n x n board so that no two queens are in the same row, column, or diagonal. Sample x 4 queens on 4 x 4 x x x Search Tree Example of 4 queens on 4 x 4 x  x x x  x x x  x x x x x  x x x x x x x x  x x x x x x x x  x x x x x x x x  x x x x x x x x  x x x x x x x x x  x x x x x x x x x x x  x x x x x x x x x x x x x x  x x x x x x x x x x x x x x x x x x Running Time Analysis The heart and soul of our running time analysis is all derived from recursive calls. Inside our setup method where all variables are set to their default values is the recursive method is called once. However, what about the recursive method itself? The Recursive Method Analyzation When 𝑘 = 0 the recursive method is called one time from solveNQueen() When 𝑘 > 0, there are 𝑛 𝑛 − 1 … 𝑛 − 𝑘 + 2 ways to place 𝑘 − 1 queens in the first 𝑘 − 1 columns in different rows. 𝑛 𝑛−1 … 𝑛−𝑘+2 Ignoring Recursion Component of our Recursive Method Our recursive method has one for loop that goes up to n, which can be represented as Θ 𝑛 for 𝑘 < 𝑛, therefore, the worst-case is at most 𝑛, for 𝑘 = 1, and 𝑛 𝑛 𝑛 − 1 … 𝑛 − 𝑘 + 2 , for 1 < 𝑘 < 𝑛 When 𝑘 = 𝑛 − 1, all rows except for one are occupied. This means our positionOk method should return true for one call. Our recursive method runs 𝑂 𝑛 when 𝑘 = 𝑛 − 1 There are 𝑛 𝑛 − 1 … 2 ways to place 𝑛 − 1 queens in the first 𝑛 − 1 columns in different rows. Therefore the worst-case for our recursive call solveNQueen(n - 1) is 𝑛 𝑛 𝑛−1 … 2 Now let’s put together our recursive analysis Combining the equations from the previous slides, we can find the worst-case time overall. 𝑛 1 + 𝑛 + 𝑛 𝑛 − 1 + ⋯+ 𝑛 𝑛 − 1 …2 1 1 1 1 𝑛 ∗ 𝑛! + + + 𝑛! 𝑛−1 ! 𝑛 − 2 ! 1! ∞ This you should 1 learn from 𝑒=෍ Calculus 𝑖! 𝑖=0 Now let’s put together our recursive analysis Combining the equations from the previous slides, we can find the worst-case time overall. That 𝑛 1 + 𝑛 + 𝑛 𝑛 − 1 + ⋯+ 𝑛 𝑛 − 1 …2 1 1 1 1 Means… 𝑛 ∗ 𝑛! + + + 𝑛! 𝑛−1 ! 𝑛 − 2 ! 1! ∞ This you should 1 learn from 𝑒=෍ Calculus 𝑖! 𝑖=0 Now let’s put together our recursive analysis 𝑛 1 + 𝑛 + 𝑛 𝑛 − 1 + ⋯+ 𝑛 𝑛 − 1 …2 1 1 1 1 𝑛 ∗ 𝑛! + + + 𝑛! 𝑛−1 ! 𝑛 − 2 ! 1! This you should ∞ learn from 1 Calculus 𝑒=෍ 𝑖! 𝑖=0 ∞ 1 1 1 1 1 𝑛 ∗ 𝑛! + + + = 𝑛 ∗ 𝑛! ෍ = 𝑛 ∗ 𝑛! (𝑒 − 1) 𝑛! 𝑛−1 ! 𝑛 − 2 ! 1! 𝑖! 𝑖=0 Now let’s put together our recursive analysis 𝑛 1 + 𝑛 + 𝑛 𝑛 − 1 + ⋯+ 𝑛 𝑛 − 1 …2 The Running Time 𝑛 ∗ 𝑛! 1 𝑛! + 1 𝑛−1 ! + 1 + 1 𝑛 − 2 ! 1! is 𝑂 𝑛 ∗ 𝑛! !!!! This you should learn from Calculus 𝑒=෍ ∞ 1 𝑖! 𝑖=0 ∞ 1 1 1 1 1 𝑛 ∗ 𝑛! + + + = 𝑛 ∗ 𝑛! ෍ = 𝑛 ∗ 𝑛! (𝑒 − 1) 𝑛! 𝑛−1 ! 𝑛 − 2 ! 1! 𝑖! 𝑖=0 The Skeleton Backtracking Algorithm This is a skeleton backtracking algorithm you can utilize in design your backtracking solutions to various problems bound() tests for a partial solution backtrack(n) rbacktrack(k, n) rbacktrack(1,n) for each x[k] ∈ S if (bound(k)) if (k == n) //output the solution for i = 1 to n print(x[i] + “ ”) println() else rbacktrack(k+1,n)  COP3503C Computer Science 2 Dr. Andrew Steinberg Asymptotic Notation and Recurrences Background Story of this Recitation During our first two lecture sessions, we covered tons of mathematical theory behind al- gorithm analysis and design. We looked at 3 formal asymptotic notations which allows us to derive computation complexity in terms of running time and space usage which we are now going to see throughout the remainder of the course. We also looked recurrences which are used widely in recursion problems (such as divide and conquer and backtracking). This lab is to help you build your mathematical skills in formally proving asymptotic notations and solving recurrences. This will help you get ready for the remainder of the course content we are going to be covering! Asymptotic Notation Analogies Determine if the following runtimes can be formally bounded in the provided respective asymptotic notation. You do not need to formally prove it, you just have to answer yes or no. 1. 3n2 − 100n + 6 = O(n2 ) 2. 3n2 − 100n + 6 = Θ(n4 ) 3. 3n2 − 100n + 6 = Ω(n3 ) 4. 2n+1 = Θ(2n ) 1 of 4  COP3503C Computer Science 2 Dr. Andrew Steinberg Asymptotic Notation and Recurrences Asymptotic Notation For the following given functions, use the formal definition presented in class to prove its respective notation bound. 1. 5n2 − 24 = O(n3 ) 2. 6n2 − 5 = Θ(n2 ) 2 of 4  COP3503C Computer Science 2 Dr. Andrew Steinberg Asymptotic Notation and Recurrences 3. 2n3 − 25n2 = Ω(n) Recurrences (Master Theorem) Solve the following recurrences by applying Master Theorem. Make sure to claim which case you used along with the constant c. 1. T (n) = T ( 3n 5 ) + 100