9780023606922, Chapter 2 3, Problem 1E

Prévia do material em texto

Chapter 2.3, Problem 1E Step-by-step solution Step 1 of 8 Consider the following expression to determine the theta Step 2 of 8 The specified expression to find theta notation is as follows : 6n+1. Step 3 of 8 Now for finding the theta form of the expression, consider the following example. Here, generally we are interested in how the time grows as the input increases by an algorithm. Step 4 of 8 For example, the worst case time of an algorithm ist(n), such that = + 5n+1 for an input of size n. Now, as input size n increases, the term is approximately equal tot(n). Step 5 of 8 Ifn=100, So, =600501 And, =600000 Step 6 of 8 According to our example, we can say that t(n) grows like and t(n) is of the Step 7 of 8 Now, From above we can infer that for large n, like n and t(n) is of the order n and As, if n=10 which is approximately equal to 6n = 60. So, Step 8 of 8 Hence, the theta notation of the expression