3. Asymptotic notation Big O, Omega and Theta and the corresponding litte letters Sample questions: - Given f(n)=3n+5, prove that f(n)=(n) - Find the running time of following gorithm : Solves the problem by dividing a problem of size n into five subproblems of half the size, recursively solving the subproblems, and combining the solutions in constant time. Solution: For Algorithm ,T(n)=5T(n/2)/c1, where c1 is a constant. By the Masters Theorem: - Running time of Algorithm A is (nlog25) - Show that for any real constants a and b, where b>0,(n+a)b=(nb) - Is 2n+1=O(2n) ? - Is 22n=O(2n)