Flashcards on Algorithms, Data Structures, and Numerical Methods
Algorithms, Data Structures, and Numerical Methods Explained
Tap to flip · Swipe to navigate
Algorithms
17 cards
Card 1
Question: Using the Master Theorem, what is the asymptotic complexity of T(n)=7T(n/4)+n^2 ?
Answer: T(n)=Θ(n^2). (Compare n^{log_4 7}≈n^{1.404} to f(n)=n^2; f(n) dominates so T(n)=Θ(f(n)).)
Card 2
Question: Using the Master Theorem, what is the asymptotic complexity of T(n)=3T(n/10)+n ?
Answer: T(n)=Θ(n). (Here n^{log_{10}3}≈n^{0.477}<n, so f(n)=n dominates and T(n)=Θ(n).)
Card 3
Question: Using the Master Theorem, what is the asymptotic complexity of T(n)=9T(n/3)+n^2 ?
Answer: T(n)=Θ(n^2 log n). (n^{log_3 9}=n^2 matches f(n)=n^2, so T(n)=Θ(n^2 log n)).
Card 4
Question: Using the Master Theorem, what is the asymptotic complexity of T(n)=7T(n/2)+n^2 ?
Answer: T(n)=Θ(n^{log_2 7}). (Here n^{log_2 7}≈n^{2.807}>n^2, so T(n)=Θ(n^{log_2 7}).)
Card 5
Question: What is the asymptotic complexity of T(n)=T(√n)+2 ?
Answer: T(n)=Θ(log log n). (Recurrence reduces n to √n each step, so number of steps is O(log log n); constant work per step.)
Card 6
Question: Is 2^{n+1} = O(2^n)? Provide the answer.
Answer: Yes. 2^{n+1}=2·2^n, so it's Θ(2^n) and therefore O(2^n).
Card 7
Question: Is 2^{2n} = O(2^n)? Provide the answer.
Answer: No. 2^{2n}=(2^n)^2 grows exponentially faster; the ratio 2^{2n}/2^n=2^n goes to infinity, so 2^{2n} is not O(2^n).
Card 8
Question: For the simple trial division primality test that checks divisibility by i from 2 to floor(√n), what is the worst-case time complexity?
Answer: Worst-case time complexity: O(√n) divisions (when n is prime or has no small divisor), so O(√n).
Card 9
Question: For the same primality test, what is the best-case time complexity?
Answer: Best-case time: Ω(1) — discovery of a small divisor (e.g., divisible by 2) in the first iteration, returning quickly.
Card 10
Question: Give one common method to reduce the number of divisions in the trial-division primality test.
Answer: Only test divisibility by 2 and then odd numbers (skip even i), or test only by primes up to √n (use a precomputed list of primes). This reduces the n