6) The following rules can be used to simplify the task of obtaining a big-O characterization...

 

Transcribed Image Text:

6) The following rules can be used to simplify the task of obtaining a big-O characterization for various algorithms: 1. If d(n) is O(f(n)), then ad(n) is O(f(n)), for any constant a > 0. 2. If d(n) is O(f(n)) and e(n) is O(g(n)), then d(n)+e(n) is O(f(n)+g(n)). 3. If d(n) is O(f(n)) and e(n) is O(g(n)), then d(n)e(n) is O(f(n)g(n)). 4. If d(n) is O(f(n)) and f(n) is O(g(n)), then d(n) is O(g(n)). ...+and). 5. If f(n) is a polynomial of degree d (that is, f(n)= ao+an+ then f(n) is O(nd). 6. n is O(a") for any fixed a>0 and a > 1. 7. log n is O(log n) for any fixed > 0. 8. log n is O(n) for any fixed constants a > 0 and y > 0. Use the big-O notation to estimate the time complexity for the following. a. a(n) = b(n)c(n), where b(n) = n +3 and c(n) = n +1 b. a(n) = b(n) + c(n), where b(n) = n + n5 +n+ 1000 and c(n) = 5000m - 3 c. a(n) = b(n)c(n), where b(n) = 2n and c(n) = 3 log n 6) The following rules can be used to simplify the task of obtaining a big-O characterization for various algorithms: 1. If d(n) is O(f(n)), then ad(n) is O(f(n)), for any constant a > 0. 2. If d(n) is O(f(n)) and e(n) is O(g(n)), then d(n)+e(n) is O(f(n)+g(n)). 3. If d(n) is O(f(n)) and e(n) is O(g(n)), then d(n)e(n) is O(f(n)g(n)). 4. If d(n) is O(f(n)) and f(n) is O(g(n)), then d(n) is O(g(n)). ...+and). 5. If f(n) is a polynomial of degree d (that is, f(n)= ao+an+ then f(n) is O(nd). 6. n is O(a") for any fixed a>0 and a > 1. 7. log n is O(log n) for any fixed > 0. 8. log n is O(n) for any fixed constants a > 0 and y > 0. Use the big-O notation to estimate the time complexity for the following. a. a(n) = b(n)c(n), where b(n) = n +3 and c(n) = n +1 b. a(n) = b(n) + c(n), where b(n) = n + n5 +n+ 1000 and c(n) = 5000m - 3 c. a(n) = b(n)c(n), where b(n) = 2n and c(n) = 3 log n