Homework Answers
1. Which explanation matches the following runtime complexity
?
T(N)= k + T(N-1)
Answer:- (b). Every time the function is called , k
operations are done,
and the recursive call lowers N by 1.
explanation:- Let N=10, At starting k operations
complete then again recursive
call with N-1, in next N-2 , in next N-3 ......... 1.
Add Answer to:
which explanation matches the following runtime complexity? T(N)=k+T(N-1) a. Every time the function is called, k...
6. Which of the following best describes the runtime complexity of the following scenario: A person...
6. Which of the following best describes the runtime complexity of the following scenario: A person has to put n tent stakes into the ground. The tent stakes are to be placed 1 meter apart. Each step in this process involves walking 1 meter and driving a stake into the ground. Assume that the n stakes are placed in a backpack and carried along the way. The runtime complexity (in terms of the distance walked as a function of the...
Let T(n) be the runtime of the following RaiseToPower() function that computes baseVal raised to the...
Let T(n) be the runtime of the following RaiseToPower() function that computes baseVal raised to the n-th power. int RaiseToPower (int baseval, int n){ int resultval; if (n == 0) { resultval = 1; } else { resultval = baseval - RaiseToPower (baseval, n-1 ); return resultval; } Which of the following is correct about T(n)? There are more than one correct answers. Select one or more: a. T(n) = CO, if n=0. (CO is a small constant variable.) b....
The task was to find the recurrence relation for this function and then find the complexity...
The task was to find the recurrence relation for this function and then find the complexity class for it as well. Provided is my work and the function. My question is, I feel like I'm missing some step in the recurrence relation and complexity class. Is this correct? The following code is in JavaScript. function divideAndConquerSum(x){ if(x.length<1){ return 0; } if(x.length == 1){ return x[0]; } var third = Math.floor((x.length-1)/3); var next = (third *2)+1; var y = x.slice(0, third+1);...
Compute the time complexity for each of the following two program fragments with respect to N....
Compute the time complexity for each of the following two program fragments with respect to N. Show your steps in reaching your answer. 1) for(i=1; i < N; i = i*2) { for(j=0;j // Operations with constant time… } } 2) for(i = 0; i < sqrt(N); i++){ for(j=1; j < i+8; j++){ for(k=0;k // Operations with constant time… } } }
Please answer ALL parts completely-- answer with clear explanation will get a thumbs up! Problem 2:...
Please answer ALL parts completely-- answer with clear
explanation will get a thumbs up!
Problem 2: Programming [2 points] Consider the following pseudo code where a function has been defined for a non negative integer x. Note that the function calls itself (within the while loop) making it a recursive function. def func (x) print x while i<x: i = i+1 func (x-1) (a) How many times does the program print if we call func (0) and func (1), respectively?...
Part A Analyze the following recurrences and show their time complexity functions using (I) iteration method...
Part A Analyze the following recurrences and show their time complexity functions using (I) iteration method and (2) Master Theorem. AI. T(n) = 2T 3 A2. T(n) = 3T 2n АЗ. Т(п) — Т(п — 2) + 3 А4. Т(п) — 2Т (п — 1) + 1 A5. T(n)= 4T +n log n A6. T(n) = 3T +n log n n2 A7. T(n) = 27 Part B Do 2.3-4 (р39) and Problem 2-1 (р39) Part C Implement MERGE-SORT() algorithm that...
Question 3: Given the following two code fragments [2 Marks] (i)Find T(n), the time complexity (as...
Question 3: Given the following two
code fragments [2 Marks]
(i)Find T(n), the time complexity (as
operations count) in the worst case?
(ii)Express the growth rate of the
function in asymptotic notation in the closest bound possible.
(iii)Prove that T(n) is Big O (g(n)) by
the definition of Big O
(iv)Prove that T(n) is (g(n)) by using
limits
What is the time-complexity of the algorithm abc? Procedure abc(n: integer) s := 0 i :=1...
What is the time-complexity of the algorithm abc? Procedure abc(n: integer) s := 0 i :=1 while i ≤ n s := s+1 i := 2*i return s consider the following algorithm: Procedure foo(n: integer) m := 1 for i := 1 to n for j :=1 to i2m:=m*1 return m c.) Find a formula that describes the number of operations the algorithm foo takes for every input n? d.)Express the running time complexity of foo using big-O/big-
ld ts biovs Part II: Analysis of recursive algorithms is somewhat different from that of non-recursive...
ld ts biovs Part II: Analysis of recursive algorithms is somewhat different from that of non-recursive algorithms. We are very much interested in how many times the method gets called. The text refers to this as the number of activations. In inefficient algorithms, the number of calls to a method grows rapidly, in fact much worse than algorithms such as bubble sort. Consider the following: public static void foo ( int n ) { if n <=1 ow ura wor...
(20 points) Recall the following deterministic select algorithm: (a) Divide the n elements into groups of...
(20 points) Recall the following deterministic select algorithm:
(a) Divide the n elements into groups of size 5. So n/5 groups. (b)
Find the median of each group. (c) Find the median x of the n/5
medians by a recursive call to Select. (d) Call Partition with x as
the pivot. (e) Make a recursive call to Select either on the
smaller elements or larger elements (de- pending on the situation);
if the pivot is the answer we are done....
6. Which of the following best describes the runtime complexity of the following scenario: A person has to put n tent stakes into the ground. The tent stakes are to be placed 1 meter apart. Each step in this process involves walking 1 meter and driving a stake into the ground. Assume that the n stakes are placed in a backpack and carried along the way. The runtime complexity (in terms of the distance walked as a function of the...
Let T(n) be the runtime of the following RaiseToPower() function that computes baseVal raised to the n-th power. int RaiseToPower (int baseval, int n){ int resultval; if (n == 0) { resultval = 1; } else { resultval = baseval - RaiseToPower (baseval, n-1 ); return resultval; } Which of the following is correct about T(n)? There are more than one correct answers. Select one or more: a. T(n) = CO, if n=0. (CO is a small constant variable.) b....
Please answer ALL parts completely-- answer with clear
explanation will get a thumbs up!
Problem 2: Programming [2 points] Consider the following pseudo code where a function has been defined for a non negative integer x. Note that the function calls itself (within the while loop) making it a recursive function. def func (x) print x while i<x: i = i+1 func (x-1) (a) How many times does the program print if we call func (0) and func (1), respectively?...
Part A Analyze the following recurrences and show their time complexity functions using (I) iteration method and (2) Master Theorem. AI. T(n) = 2T 3 A2. T(n) = 3T 2n АЗ. Т(п) — Т(п — 2) + 3 А4. Т(п) — 2Т (п — 1) + 1 A5. T(n)= 4T +n log n A6. T(n) = 3T +n log n n2 A7. T(n) = 27 Part B Do 2.3-4 (р39) and Problem 2-1 (р39) Part C Implement MERGE-SORT() algorithm that...
Question 3: Given the following two
code fragments [2 Marks]
(i)Find T(n), the time complexity (as
operations count) in the worst case?
(ii)Express the growth rate of the
function in asymptotic notation in the closest bound possible.
(iii)Prove that T(n) is Big O (g(n)) by
the definition of Big O
(iv)Prove that T(n) is (g(n)) by using
limits
ld ts biovs Part II: Analysis of recursive algorithms is somewhat different from that of non-recursive algorithms. We are very much interested in how many times the method gets called. The text refers to this as the number of activations. In inefficient algorithms, the number of calls to a method grows rapidly, in fact much worse than algorithms such as bubble sort. Consider the following: public static void foo ( int n ) { if n <=1 ow ura wor...
(20 points) Recall the following deterministic select algorithm:
(a) Divide the n elements into groups of size 5. So n/5 groups. (b)
Find the median of each group. (c) Find the median x of the n/5
medians by a recursive call to Select. (d) Call Partition with x as
the pivot. (e) Make a recursive call to Select either on the
smaller elements or larger elements (de- pending on the situation);
if the pivot is the answer we are done....
Most questions answered within 3 hours.
-
A local
electronic company primarily manufactures four highly technical
telecommunication products. Each product must be processed...
asked 46 minutes ago -
•Describe the basic structure of collagen monomers •Explain how
amino acid composition of collagen contributes to...
asked 2 hours ago -
Compute the sample correlation coefficient
r for each of the following data sets.
(Use 3 decimal...
asked 3 hours ago -
5a. What are the advantages and disadvantages of Proxy ARP?
b. What is the TTL field...
asked 2 hours ago -
An ice cube (density = 900[kg/m3]) with a side length of
2.54[cm] is held by a...
asked 4 hours ago -
would you say that leaders in the international context are born
or made? That is, can...
asked 4 hours ago -
Instructions
Read the Digital Trends article "Solid state drives are speedier
than hard disk drives. Are...
asked 4 hours ago -
A multiple-choice test consists of 29 questions with possible
answers of a, b, c, d. Estimate...
asked 5 hours ago -
Question 1: Ethanol is the active ingredient of alcoholic
beverages. It is also s a possible...
asked 5 hours ago -
In the process of a simple distillation, the substances in the
still head tube are in...
asked 5 hours ago -
In a normal distribution with mean 3 and standard deviation of
7, what are the upper...
asked 5 hours ago -
A big block stone with mass M explodes and splits in two pieces
with mass 0.40M...
asked 5 hours ago