The input has three numbers a, b, c. And we have an algorithm that runs in...
The input has three numbers a, b, c. And we have an algorithm that runs in time at most 2·log a+b 1/3+(log c) 3 . Does the algorithm run in polynomial time? Explain.
Homework Answers
Yes the algorithm can run in a polynomial time.
An algorithm runs in a polynomial time if it's maximum run time on inputs of size n is Cn^k where C,k>0.
In given statement the time complexity of the algorithm is T= 2loga+b/3+3logc and inputs are a,b,c.
and the time complexity equation is in terms of inputs those have been given to the algorithm.
proof::
If all the inputs a,b,c are equal then then the equation T=2logb+b/3+3logb would be like this T=5logb+b/3.
In case of time complexities only higher order terms are considered ,So the time complexity of the algorithm is O(b),It is a polynomial time.
Add Answer to:
The input has three numbers a, b, c. And we have an algorithm
that runs in...
The input consists of n numbers a1, a2, . . . , an and a target...
The input consists of n numbers a1, a2, . . . , an and a target value t. The goal is to determine in how many possible ways can we add up two of these numbers to get t. Formally, your program needs to find the number of pairs of indices i, j, i < j such that ai+aj = t. For example, for 2, 7, 3, 1, 5, 6 and t = 7, we can get t in two...
It is due in 2 hours.. Thanks ! Suppose that an algorithm runs on a tree...
It is due in 2 hours.. Thanks !
Suppose that an algorithm runs on a tree containing n nodes. What is the time complexity of the algorithm if the time spent per node in the tree is proportional to the number of grandchildren of the node? (Assume that the algorithm spends O(1) time for every node that does not have a grandchild.) In modern software development, a useful utility called make is usually employed to manage the compilation order of...
3. (10 pts) Design an algorithm how to multiply two complex numbers abi and c + di using only three multiplications of real numbers. Your algorithm should take a, b, c and d as input and produce the...
3. (10 pts) Design an algorithm how to multiply two complex numbers abi and c + di using only three multiplications of real numbers. Your algorithm should take a, b, c and d as input and produce the real component a*c-b*d and the imaginary component a*d + b*c separately MULTIPLY-COMPLEX-NUMBER(a, b, c, d)
3. (10 pts) Design an algorithm how to multiply two complex numbers abi and c + di using only three multiplications of real numbers. Your algorithm should...
help in design of algorithm answers with steps for study guide (2 points) Why shouldn't we...
help in design of algorithm
answers with steps for study guide
(2 points) Why shouldn't we measure time efficiency based on the number of seconds or milliseconds it takes the algorithm 1. to run? is the number of times the most important operation of the (2 points) The 2. algorithm occ Ccurs (3 points) Find the binary representation of the following numbers: 3. BINARY REPRESENTATION (in bits) NUMBER 777 14 684,739 4. (8 points) Write the input size metric and...
The Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to...
The Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite lie., not prime) the multiples of each prime, starting with the multiples of 2 The sieve of Eratosthenes can be expressed in pseudocode, as follows: Input: an integer n Let A be an array of 8oo1ean values, indexed by integers 2 to n, initially all set to true. for t - 2, 3,...
4.11.3 P4.11.3 Prove the claim at the end of the section about the Euclidean Algorithm and...
4.11.3
P4.11.3 Prove the claim at the end of the section about the Euclidean Algorithm and Fibonaci numbers. Specifically, prove that if positive naturals a and b are each at most F(n), then the Euclidean Algorithm performs at most n -2 divisions. (You may assume that n >2) P4.11.4 Suppose we want to lay out a full undirected binary tree on an integrated circuit chip, wi 4.11.3 The Speed of the Euclidean Algorithm Here is a final problem from number...
Give an algorithm for the following problem. The input is made up of two se- quences...
Give an algorithm for the following problem. The input is made up of two se- quences of n numbers: 01, A2, ..., an and b1,b2, ..., bn. Your algorithm should determine whether or not there is some i and j, where 1 si, j = n, such that az = bj. You should use universal hashing families , and your algorithm should run in an expected time of O(n). Provide inctification that your algorithm is correct and runs in the...
Problem 1. 1. Draw the decision tree for the merge-sort algorithm for the input consisting of...
Problem 1. 1. Draw the decision tree for the merge-sort algorithm for the input consisting of 3 numbers: a, b,c. 2. Draw the 4 top levels of the decision tree for the merge-sort algorithm for the input consisting of 4 numbers: a, b, c, d 3. How may leaves does this tree have? 4. How many levels does this tree have? 5. What is the number of comparisons needed to sort these 4 numbers by the merge-sort algorithm in the...
Lower bound arguments. In class, we proved that any comparison-based algorithm that has to sort n...
Lower bound arguments. In class, we proved that any comparison-based algorithm that has to sort n numbers runs in Ω (nlogn) time. Let’s change the problem a bit. Suppose S[1. . . n] is a sorted array. We want to know if S contains some element x. a. How would you solve this problem and what is the running time of your algorithm? (Note: you can just say what algorithm you will use.) b. Show that any comparison-based algorithm(i.e., one...
1. Prepare C++ code that prompts the user for an input integer n, creates a vector...
1. Prepare C++ code that prompts the user for an input integer n, creates a vector consisting of numbers 0,1,2,…,n-1, runs the STL algorithm random_shuffle on it and then prints out the resulting outcome, i.e. the resulting random permutation. 2. Prepare C++ code that prompts the user for an input integer n, creates a vector consisting of numbers 0,1,2,…,n-1, runs the STL algorithm random_shuffle on it and creates three copies of the resulting outcome (probably 3 .txt files).
It is due in 2 hours.. Thanks !
Suppose that an algorithm runs on a tree containing n nodes. What is the time complexity of the algorithm if the time spent per node in the tree is proportional to the number of grandchildren of the node? (Assume that the algorithm spends O(1) time for every node that does not have a grandchild.) In modern software development, a useful utility called make is usually employed to manage the compilation order of...
3. (10 pts) Design an algorithm how to multiply two complex numbers abi and c + di using only three multiplications of real numbers. Your algorithm should take a, b, c and d as input and produce the real component a*c-b*d and the imaginary component a*d + b*c separately MULTIPLY-COMPLEX-NUMBER(a, b, c, d)
3. (10 pts) Design an algorithm how to multiply two complex numbers abi and c + di using only three multiplications of real numbers. Your algorithm should...
help in design of algorithm
answers with steps for study guide
(2 points) Why shouldn't we measure time efficiency based on the number of seconds or milliseconds it takes the algorithm 1. to run? is the number of times the most important operation of the (2 points) The 2. algorithm occ Ccurs (3 points) Find the binary representation of the following numbers: 3. BINARY REPRESENTATION (in bits) NUMBER 777 14 684,739 4. (8 points) Write the input size metric and...
The Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite lie., not prime) the multiples of each prime, starting with the multiples of 2 The sieve of Eratosthenes can be expressed in pseudocode, as follows: Input: an integer n Let A be an array of 8oo1ean values, indexed by integers 2 to n, initially all set to true. for t - 2, 3,...
4.11.3
P4.11.3 Prove the claim at the end of the section about the Euclidean Algorithm and Fibonaci numbers. Specifically, prove that if positive naturals a and b are each at most F(n), then the Euclidean Algorithm performs at most n -2 divisions. (You may assume that n >2) P4.11.4 Suppose we want to lay out a full undirected binary tree on an integrated circuit chip, wi 4.11.3 The Speed of the Euclidean Algorithm Here is a final problem from number...
Give an algorithm for the following problem. The input is made up of two se- quences of n numbers: 01, A2, ..., an and b1,b2, ..., bn. Your algorithm should determine whether or not there is some i and j, where 1 si, j = n, such that az = bj. You should use universal hashing families , and your algorithm should run in an expected time of O(n). Provide inctification that your algorithm is correct and runs in the...
Most questions answered within 3 hours.
-
Given input { 66, 28, 43, 29, 44, 69, 19 } and a hash function
h(x)...
asked 8 minutes ago -
A pebble with mass m is thrown straight up with an initial speed
v0 so that...
asked 12 minutes ago -
Let X be a discrete random variable that follows a
binomial distribution with n = 11...
asked 20 minutes ago -
The equilibrium constant, K, for the following reaction is
1.29×10-2 at 600
K.
COCl2(g) --->
CO(g)...
asked 33 minutes ago -
It is known that 72% of people have a favorable opinion of their
local police force....
asked 36 minutes ago -
A vertical straight wire carrying an upward 26-A current exerts
an attractive force per unit length...
asked 49 minutes ago -
For the purposes of this assignment, you are to choose an
adaptive trait common to more...
asked 58 minutes ago -
Two identical flutes can play middle C (262 Hz) at 20◦C. How
many beats per second...
asked 1 hour ago -
Potassium phosphate and calcium chloride react in a double
replacement reaction. To produce 1.0 moles of...
asked 1 hour ago -
Sparky, Co. purchased land as a factory site for $600,000.
Sparky paid $42,000 to tear down...
asked 1 hour ago -
A Chi-square distribution with 14 degrees of freedom is a
correct model for
Question 8 options:...
asked 1 hour ago -
In a group of 45 mice, there are 10 that have a certain genetic
character. suppose...
asked 1 hour ago