For an O(Nk ) algorithm, where k is a positive integer, an instance of size M...
For an O(Nk ) algorithm, where k is a positive integer, an instance of size M takes 32 seconds to run. Suppose you run an instance of size 2M and find that it takes 512 seconds to run. What is the value of k?
Homework Answers
So changing the size from M to 2M or in other words, doubling the size, makes the time increase by 512/32 = 16 times
Which means it increases by a factor of 2^4, So K value is equal
to 4.
Hence algorithm complexity is O(N^4), which means on doubling the
size, time increases by 2^4 times.
Add Answer to:
For an O(Nk ) algorithm, where k is a positive integer, an
instance of size M...
Problem 2.15. A certain algorithm takes 10-4 2n seconds to solve an instance of size n. Show that in a year it could just solve an instance of size 38. What size of instance could be solved in a year...
Problem 2.15. A certain algorithm takes 10-4 2n seconds to solve an instance of size n. Show that in a year it could just solve an instance of size 38. What size of instance could be solved in a year on a machine one hundred times as fast? A second algorithm takes 10-2 x n3 seconds to solve an instance of size n. What size instance can it solve in a year? What size instance could be solved in a...
You are given a set of integer numbers A = {a1, a2, ..., an}, where 1...
You are given a set of integer numbers A = {a1, a2, ..., an}, where 1 ≤ ai ≤ m for all 1 ≤ i ≤ n and for a given positive integer m. Give an algorithm which determines whether you can represent a given positive integer k ≤ nm as a sum of some numbers from A, if each number from A can be used at most once. Your algorithm must have O(nk) time complexity.
Prove that if N = Π. 1 n t such that nk where ni, n2..-m are positive integers, there exsts some ...
Prove that if N = Π. 1 n t such that nk where ni, n2..-m are positive integers, there exsts some integer VN. (Here. ITal ni = ning 4 k nt.)
Prove that if N = Π. 1 n t such that nk where ni, n2..-m are positive integers, there exsts some integer VN. (Here. ITal ni = ning 4 k nt.)
Suppose you are given k sorted arrays of size n. Give an algorithm, that runs in...
Suppose you are given k sorted arrays of size n. Give an algorithm, that runs in O(nk log k)time, that merges them into a single list.
Please show steps with explanations 3. Find the smallest positive integer k such that 1222+32++ n2...
Please show steps with explanations
3. Find the smallest positive integer k such that 1222+32++ n2 is big-O of nk. Explain.
Suppose that an algorithm has run-time proportional to 2n , where n is the input size....
Suppose that an algorithm has run-time proportional to 2n , where n is the input size. The algorithm takes 1 millisecond to process an array of size 10. How many milliseconds would you expect the algorithm take to process an array of size 20 ?
Write an algorithm that takes two strings X and Y and a positive integer k as...
Write an algorithm that takes two strings X and Y and a positive integer k as input, and determines whether Y can be turned into X by at most k insertions or deletions. For example: let X = “abacad", Y = “cebacad" and k = 3 then your algorithm should give a yes answer because Y can be turned into X in 3 steps by a left-to-right processing as follows: delete leftmost c delete “e" insert “a" Give an tight...
Suppose that, in a divide-and-conquer algorithm, we always divide an instance of size n of a...
Suppose that, in a divide-and-conquer algorithm, we always
divide an instance of size n of a problem into 5 sub-instances of
size n/3, and the dividing and combining steps take a time
in Θ(n n). Write a recurrence equation for the running time T
(n) , and solve the
equation for T (n)
2. Suppose that, in a divide-and-conquer algorithm, we always divide an instance of size n of a problem into 5 sub-instances of size n/3, and the dividing...
9. [10 points) Consider the following algorithm: procedure Algorithm(n: positive integer; ddd: distinet integers) for k:=1 to n-1 for 1-1 to n-k print(k, I, di,da...-1,dn) if ds dti then interch...
9. [10 points) Consider the following algorithm: procedure Algorithm(n: positive integer; ddd: distinet integers) for k:=1 to n-1 for 1-1 to n-k print(k, I, di,da...-1,dn) if ds dti then interchange dy and d (a) Assume that this algorithm receives as input the integer n 6 and the input sequence 하하하하하하, Miss ^-ruteae rehen i12|3141516 Fill out the table below: ds ds (b) Assume that the algorithm receives the same input values as in part a). Once the algorithm finishes, what...
8. [10 points) Consider the following algorithm procedure Algorithm(: integer, n: positive integer; 81,...a s integers with vhilei<r print (l, r, mı, arn, 》 if z > am then 1:= m + 1 if za...
8. [10 points) Consider the following algorithm procedure Algorithm(: integer, n: positive integer; 81,...a s integers with vhilei<r print (l, r, mı, arn, 》 if z > am then 1:= m + 1 if za then anstwer-1 return answer 18 and the (a) Assume that this algorithm receives as input the numbersz-32 and corresponding sequence of integers 2 | 3 1 1 4151617| 8| 9 | 10 İ 11 İ 12 | 13 | 14|15 | 16 | 17 |...
Problem 2.15. A certain algorithm takes 10-4 2n seconds to solve an instance of size n. Show that in a year it could just solve an instance of size 38. What size of instance could be solved in a year on a machine one hundred times as fast? A second algorithm takes 10-2 x n3 seconds to solve an instance of size n. What size instance can it solve in a year? What size instance could be solved in a...
Prove that if N = Π. 1 n t such that nk where ni, n2..-m are positive integers, there exsts some integer VN. (Here. ITal ni = ning 4 k nt.)
Prove that if N = Π. 1 n t such that nk where ni, n2..-m are positive integers, there exsts some integer VN. (Here. ITal ni = ning 4 k nt.)
Please show steps with explanations
3. Find the smallest positive integer k such that 1222+32++ n2 is big-O of nk. Explain.
Suppose that, in a divide-and-conquer algorithm, we always
divide an instance of size n of a problem into 5 sub-instances of
size n/3, and the dividing and combining steps take a time
in Θ(n n). Write a recurrence equation for the running time T
(n) , and solve the
equation for T (n)
2. Suppose that, in a divide-and-conquer algorithm, we always divide an instance of size n of a problem into 5 sub-instances of size n/3, and the dividing...
9. [10 points) Consider the following algorithm: procedure Algorithm(n: positive integer; ddd: distinet integers) for k:=1 to n-1 for 1-1 to n-k print(k, I, di,da...-1,dn) if ds dti then interchange dy and d (a) Assume that this algorithm receives as input the integer n 6 and the input sequence 하하하하하하, Miss ^-ruteae rehen i12|3141516 Fill out the table below: ds ds (b) Assume that the algorithm receives the same input values as in part a). Once the algorithm finishes, what...
8. [10 points) Consider the following algorithm procedure Algorithm(: integer, n: positive integer; 81,...a s integers with vhilei<r print (l, r, mı, arn, 》 if z > am then 1:= m + 1 if za then anstwer-1 return answer 18 and the (a) Assume that this algorithm receives as input the numbersz-32 and corresponding sequence of integers 2 | 3 1 1 4151617| 8| 9 | 10 İ 11 İ 12 | 13 | 14|15 | 16 | 17 |...
Most questions answered within 3 hours.
-
using RECURSIVE Functions in Java, create a public static String
doubleLetters (String word)
For ex) that...
asked 4 minutes ago -
With a $16 Trillion national ebt, and projected annual budget
eficits in excess of $1 Trillion...
asked 18 minutes ago -
A machine shop owner wishes to assign each of three machinists
(labeled 1, 2, and 3)...
asked 32 minutes ago -
Regarding language development, which of the following
statements is FALSE?
Babies are able to cry from...
asked 32 minutes ago -
A couple of small ice cubes at 0 °C are added to glass of warm
water...
asked 30 minutes ago -
Slow 'n Steady, Inc., has a stock price of $30, will pay a
dividend next year...
asked 33 minutes ago -
During the current financial year, the owner of Omega
Enterprises withdrew supplies of $2,000 for personal...
asked 29 minutes ago -
PLEASE SHOW MATH CALCULATION(formulas)it has to be done on excel
P12-4 Last year (2016), Richter Condos...
asked 38 minutes ago -
A 0.25μF capacitor is charged to 50 V . It is then connected in
series with...
asked 54 minutes ago -
Calculate the current, I, through the batteries for:
- a 2-bulb parallel circuit
- How does...
asked 55 minutes ago -
Choose the sentence that uses correct punctuation.
1a. The prefatory parts of a report include the...
asked 1 hour ago -
For the element arsenic, which one of the following sets of
quantum numbers could not apply...
asked 1 hour ago