Question

6. Let t be a positive integer. Show that 1? + 2? + ⋯ + (? − 1)? + ?? is ?(??+1).

7. Arrange the functions ?10, 10?, ? log ? , (log ?)3, ?5 + ?3 + ?2, and ?! in a list so that each function is big-O of the next function.

8. Give a big-O estimate for the function ?(?)=(?3 +?2log?)(log?+1)+(5log?+10)(?3 +1). For the function g in your estimate f(n) is O(g(n)), use a simple function g of smallest order.

9. Prove that 2x4 + 4x2 + 1 is (x4).

10. Show that 10x3 + 4x + 7 is (x3) by directly finding the constants k, C1, and C2 in the definition “f(x) is (g(x)) if and only if there are positive constants k, C1, and C2 such that C1|g(x)|  |f(x)|  C2|g(x)| whenever x  k”.

SECTION 3.3 Complexity of Algorithms

11. Give a big-O estimate for the number of additions used in this segment of an algorithm. s := 0 for i := 1 to n for j := 1 to n s := s + i + j

12. Give a big-O estimate for the number of operations, where an operation is an addition or multiplication, used in this segment of an algorithm (ignoring comparisons used to test the conditions in the while loop). i := 1 s := 0 while i  n 2 s := s + i i := 2i

13. Given a real number x and a positive integer k, determine the number of multiplications used to find ?2? starting with x and successively squaring (to find x2, x4, x8, and so on). Is this a more efficient way to find ?2? than by multiplying x by itself the appropriate number of times?

14. Determine the least number of comparisons, or best-case performance,

a) required to find the maximum of a sequence of n integers, using Algorithm 1 of Section 3.1.

b) used to locate an element in a list of n terms with a linear search.

15. What is the effect of the time required to solve a problem when you double the size of the input from n to 2n, assuming that the number of milliseconds the algorithm uses to solve the problem with input size n is each of these functions?

a) n3

b) 2n

Answer 1

6.

1t + 2t + 3t + 4t + 5t + 6t + 7t + .... + (n-1)t + nt ; t > 0;

= (1 + 2 + 3 + 4 +5 + 6 + 7 + ...... + (n-1) + n )t ;

= ((n (n + 1) ) / 2 ) t

= (n² + n)t / 2;

= O(n²t )

7. It is saying each function is big O of next function i.e to arrange in ascending order;

After arranging: (logx)³ < 10x < xlogx < x⁵ + x³ + x² < x¹⁰ < x!

= (logx)³ = O(10x) = O(xlogx) = O(x⁵ + x³ + x²) = O(x¹⁰) = O(x!)

8.

  ?(?)=(?3 +?2log?)(log?+1)+(5log?+10)(?3 +1)

= (n³ + n²logn)(logn + 1) + (5logn + 10)(n³ + 1)

= n³logn + n³ + n²(logn)² + n²logn + 5n³logn + 5logn + 10n³ + 10

= n³ (6logn + 11) + n² ((logn)² + (logn)) + 5logn + 10

=  n³ (6logn + 11) (ignoring the lower order term)

= O(n³logn)

g(n) = n³logn

9. 2x⁴ + 4x² + 1 = (x⁴) //( not visible in the question, taking )

big Omega function gives the lower bound of a function; i.e 0 <= c*g(n) <= f(n) ; for n <= n0, c =a constant

f(n) = 2x⁴ + 4x² + 1 > g(n) = x⁴ ;

let x = 0;

2*(0) + 4 * (0) + 1 > (0)

1 > 0

in f(n) , 2x⁴ and 4x² always give a positive number, so 2x⁴ + 4x² is always greater than x⁴

so 2x⁴ + 4x² + 1 = (x⁴)

10 10x³ + 4x + 7 = (x³)

Theta notation states; there lies two constants c1 , c2 for which c1 g(x) <= f(x) <= c2 g(x) , for all x > k;

c1x³ <= 10x³ + 4x + 7 <= c2x³

to find c1, take the coefficient of the largest term and subtract all the negative coefficient terms from it;

but here no negative terms, so simply take the coefficient of x³ i . 10

c1 = 10;

to find c2 = add all the coefficients i.e 10 + 4 + 7 = 21;

c2 = 21;

10x³ < 10x³ + 4x + 7 < 21x³

when x = 0 : values = 0 , 7 , 0 ( 0 < 7 > 0)

when x =1 : values = 10 , 21 , 21 ( 10 < 21 <=21)  

so k = 1

<c1,c2,k> = <10,21,1>

11. Inner for loop will run n times and outer for loop will run n times;

so total n * n = n² time it will run;

so complexity = O(n²)