COEN 179 Lecture Notes - Lecture 23: Eval, Subset, Polynomial

• School: Santa Clara University
• Department: Computer Engineering
• Course: COEN 179
• Professor: Tran

Document Summary

This is hard, because we have to consider all possible algorithms. However, for some problems, we can prove optimally for certain classes of algorithms. Def: a lower bound for a given problem is a necessary requirement on the computation needed to solve that problem. N (f(n)) is tight if there is an algorithm for the problem that runs on time o(f(n)) In other words, a tight lower bound is necessary and sufficient. Note: lower bounds are properties of problems, not algorithms. 1)trivial lower bounds based on the input or output size of the problem. any algorithm for the problem must spend that much time to read and write data. e. g. generating subsets. Output: all subsets of {1, 2, , n} Subsets of {1, 2, 3} are: , {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} n = 0. A lower bound of (2^n) is based on the output size.