For each of the following functions, indicate the class T(g(n)) the function belongs to. Use the...

Question

For each of the following functions, indicate the class T(g(n)) the function belongs to. Use the simplest g(n) possible in your answers.  a.) b.) c.) d.)  	Find the order of growth of the following sums.  a.) b.)  	Consider the following recursive algorithm.   ALGORITHM  //Input: A positive integer nif return 2else return a.) What value is returned when n = 4?b.) Set up a recurrence relation for the number of multiplications made by this algorithm and solve it.  	   	Hypothesize a likely efficiency class of an algorithm based on the following empirical observations of its basic operation's count.     	 		 			Size 			1000 			2000 			3000 			4000 			5000 			6000 		 		 			Count 			1,021 			4,003 			9,011 			15,992 			24,797 			36,134 		 	  
	
Document Preview: For each of the following functions, indicate the class T(g(n)) the function belongs to. Use the simplest g(n) possible in your answers.		a.)	n4-3n+2	b.)	3n6-4n+70	c.)	2n+n3	d.)	logn+n2+nlognFind the order of growth of the following sums.		a.)	i=1n(i2-2i+3)3	b.)	i=1nj=1i1Consider the following recursive algorithm.	ALGORITHM	  Q(n)	//Input: A positive integer n	if  n=1 return 2	else return  Qn-1+4*n-2	a.)	What value is returned when n = 4?b.)	Set up a recurrence relation for the number of multiplications made by this algorithm and solve it.c.)	What is the efficiency class of this algorithm, based on your answer in part c?Hypothesize a likely efficiency class of an algorithm based on the following empirical observations of its basic operation's count.	Size100020003000400050006000Count1,0214,0039,01115,99224,79736,134

Robert · Accepted Answer

More problems 1 
1. For each of the following functions, indicate the class Θ(g(n)) the function belongs to. 
Use the simplest g(n) possible in your answers.
The simplest g(n) and the k1, k2 and n0 values have been indicated alongside each answer. 
 a.)         :  n4 – 3n  (k1= 1, k2=2, n0 =2) 
 b.) √          :  n3  (k1= 1, k2=3, n0 =2) 
 c.)        :   2n     (k1= 1, k2=2, n0 =10) 
 d.)               :   n2  (k1= 1, k2=2, n0 =2) 

2. Find the order of growth of the following sums. 
  
 a.) ∑                
  
b.) ∑ ∑      
 

a) The sum is of order i
6
 thus on summing the terms we get a sum in n with the resulting 
expression being a polynomial in n with highest degree 7. Thus, we have the order of growth as 
ϴ(  ). 
b) ∑ ∑      
 
     ∑  
 

 

 

 
 
 Thus,

For each of the following functions, indicate the class T(g(n)) the function belongs to. Use the simplest g(n) possible in your answers. a.) b.) c.) d.) Find the order of growth of the following sums....

Solution

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment

Size	1000	2000	3000	4000	5000	6000
Count	1,021	4,003	9,011	15,992	24,797	36,134