×
Get Full Access to Discrete Mathematics And Its Applications - 7 Edition - Chapter 3.se - Problem 18e
Get Full Access to Discrete Mathematics And Its Applications - 7 Edition - Chapter 3.se - Problem 18e

×

# 18E Find a big-O estimate for ISBN: 9780073383095 37

## Solution for problem 18E Chapter 3.SE

Discrete Mathematics and Its Applications | 7th Edition

• Textbook Solutions
• 2901 Step-by-step solutions solved by professors and subject experts
• Get 24/7 help from StudySoup virtual teaching assistants Discrete Mathematics and Its Applications | 7th Edition

4 5 1 411 Reviews
15
5
Problem 18E

?18E Find a big-?O? estimate for

Step-by-Step Solution:
Step 1 of 3

Solution: Step-1: n In this problem we need to find a big-O estimate for j(j + 1). j=1 Note: Let us consider f and g are functions from the set of integers to the set of real numbers. The estimate value can be said that f(x) is O(g(x)) if there are constants C and k such that |f(x)| C|g(x)|, where x> k.The constants C and k are called the witnesses to the relationship. The definition of f(x) is O(g(x)) says that f(x) grows slower than some fixed multiple of g(x) as x grows without bound. Step-2: n Consider , f(n) = j(j + 1). j=1 n = (j + j) j=1 n n 2 = j + j . j=1 j=1 2 2 2 2 2 = (1 + 2 + 3 + 4 + ... + n ) + (1 + 2 + 3 + 4 + ... + n) n(n+1)(2n+1) n(n+1) = 6 + 2 , here n > 1 n(n+1) 2n+1 = ( 2 )( 3 + 1) n(n+1)(2n+4) = 6 n(n+1)(n+2) = 3 Therefore ,f(n) = n(n+1)(n+2… ……(1) 3 n(n+1)(n+2) n(n+n)(n+2n) We know that , 3 3 n(2n)(3n) = 3 3 = 2n ……..(2) Step-3: From (1) , (2) we get: n(n+1)(n+2) 3 |f(n)| = 3 2n , where n> 1. 3 So, by using the above note it is clear that C = 2 , k = 1 and g(n) = n . n 3 Therefore , C= 2 and k=1 are witnesses for f(n) = j(j + 1)O(n ). j=1

Step 2 of 3

Step 3 of 3

##### ISBN: 9780073383095

This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. The answer to “?18E Find a big-?O? estimate for” is broken down into a number of easy to follow steps, and 6 words. This full solution covers the following key subjects: Big, estimate, Find. This expansive textbook survival guide covers 101 chapters, and 4221 solutions. Since the solution to 18E from 3.SE chapter was answered, more than 270 students have viewed the full step-by-step answer. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095. The full step-by-step solution to problem: 18E from chapter: 3.SE was answered by , our top Math solution expert on 06/21/17, 07:45AM.

Unlock Textbook Solution