Please find the complexity of the algorithm used to solve the problem below. Also find the...
Please find the complexity of the algorithm used to solve the problem below. Also find the approximate problem size we could solve in time t, given that we double the speed of the original machine. Thank you
Suppose that a computer can run an algorithm on a problem of size 1,024 in time t. We do not know the complexity of the algorithm. We note that when we run the same algorithm on a computer 8 times faster, in the same time t, we can solve a problem of size 8,192. We also note that when we run the same algorithm on a computer 8 times slower, in the same time t, we can solve a problem of size 128.
Homework Answers
Time Complexity of Problem - O(n)
Explanation - when n= 1024 time taken is t. on a particular computer.
When computer is 8 times faster in same time t , n can be equal to 8192. It means on increasing processing speed input grows linearly.
When computer is 8 times slow then with same time t , n will be 128 which is (1/8)th time 1024.
It means with increase in processing speed by x factor time taken will decrease by (1/x) factor. Or input size can be increased by x times. This signifies that time taken by program grows linearly with input size n. Therefore time complexity of problem will be O(n).
If we double the speed of original machine then we can solve problems of size 2n in time t.
Add Answer to:
Please find the complexity of the algorithm used to solve the
problem below. Also find the...
You are given an algorithm that uses T(n) a n2b.3" basic operations to solve a problem...
You are given an algorithm that uses T(n) a n2b.3" basic operations to solve a problem of size n, where a and b are some real non-negative constants. Suppose that your machine can perform 400,000,000 basic operations per second (a) If a = b = 1, how long does it take for your algorithm to solve problems of size n = 10, 20, 50. For each size of n, include the time in seconds and also using a more appropriate...
Please help me with this answer. Performance Comparison for Dijkstra Algorithm and Bellman-Ford Algorithm Problem Description...
Please help me with this answer. Performance Comparison for Dijkstra Algorithm and Bellman-Ford Algorithm Problem Description The shortest path problem is one of most important problems in graph theory and computer science in general. Shortest path problem is one of typical optimization problems. Given a graph G = (V,E), the goal is to nd a minimum cost path from s → t, s,t ∈ V . This variant is called one-to-one shortest path problem. Other variants are one-to-all (compute shortest...
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...
(a) Your company participates in a competition and the fastest algorithm wins. You know of two...
(a) Your company participates in a competition and the fastest algorithm wins. You know of two different algorithms that can solve the problem in the competition. • Algorithm I solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time. • Algorithm 2 solves problems of size n by dividing them into 16 subproblems of size n/4, recursively solving each subproblem, and then combining the solutions in...
Could you please help me to solve the problem. Also, could you please answer questions in...
Could you please help me to solve the problem. Also, could you please answer questions in clear hand-writing and show me the full process, thank you (Sometimes I get the answer which was difficult to read).Thanks a lot Suppose we are comparing implementations of two algorithms on the same machine. For input size of n, Algorithm A runs in 8n^2 steps, while Algorithm B runs in 64nlog2(n) steps. For what value n>2, where n is an integer, does Algorithm A...
Decrease-by-Half Algorithm We can solve the same problem using a decrease-by-half algorithm. This...
Convert the pseudocode into a C++ function
Decrease-by-Half Algorithm We can solve the same problem using a decrease-by-half algorithm. This algorithm is based on the following ideas: In the base case, n 1 and the only possible solution is b 0, e 1 In the general case, divide V into a left and rnight half; then the maximum subarray can be in one of three places: o entirely in the left half; o entirely in the right half; or o...
Could you please help me to solve the problem. Also, could you please answer questions in...
Could you please help me to solve the problem. Also, could you please answer questions in clear hand-writing and show me the full process, thank you (Sometimes I get the answer which was difficult to read).Thanks a lot What is the smallest positive value of n, where n is an integer, such that Algorithm A, whose running time is 100n2 runs faster than Algorithm B, whose running time is 2n , on the same machine (give your answer in whole number(s))
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...
Fill in the last line of the three empty rows, which shows the size of a problem can be solved in the same amount of ti...
Fill in the last line of the three empty rows, which shows the size of a problem can be solved in the same amount of time for each complexity class on a new machine that runs nine as fast as the old one. Solve by hand when you can, use Excel or a calculator when you must: I used a calculator only for O(N Log_2 N) and solved it to 3 significant digits. Solving a problem in the same amount...
1 (15 pts) Implement recursive, memoized, and dynamic programming Fibonacci and study their performances using different...
1 (15 pts) Implement recursive, memoized, and dynamic programming Fibonacci and study their performances using different problem instans You can choose to look at the perfor- mance by either timing the functions or counting the basic operations (in code) Provide your results below, and submit your code. Also, describe the pros and cons of your choice of performance metric Note: If you decide to use timing, the standard way to time an algorithm is to run the same problem 100...
You are given an algorithm that uses T(n) a n2b.3" basic operations to solve a problem of size n, where a and b are some real non-negative constants. Suppose that your machine can perform 400,000,000 basic operations per second (a) If a = b = 1, how long does it take for your algorithm to solve problems of size n = 10, 20, 50. For each size of n, include the time in seconds and also using a more appropriate...
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...
(a) Your company participates in a competition and the fastest algorithm wins. You know of two different algorithms that can solve the problem in the competition. • Algorithm I solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time. • Algorithm 2 solves problems of size n by dividing them into 16 subproblems of size n/4, recursively solving each subproblem, and then combining the solutions in...
Convert the pseudocode into a C++ function
Decrease-by-Half Algorithm We can solve the same problem using a decrease-by-half algorithm. This algorithm is based on the following ideas: In the base case, n 1 and the only possible solution is b 0, e 1 In the general case, divide V into a left and rnight half; then the maximum subarray can be in one of three places: o entirely in the left half; o entirely in the right half; or o...
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...
Fill in the last line of the three empty rows, which shows the size of a problem can be solved in the same amount of time for each complexity class on a new machine that runs nine as fast as the old one. Solve by hand when you can, use Excel or a calculator when you must: I used a calculator only for O(N Log_2 N) and solved it to 3 significant digits. Solving a problem in the same amount...
1 (15 pts) Implement recursive, memoized, and dynamic programming Fibonacci and study their performances using different problem instans You can choose to look at the perfor- mance by either timing the functions or counting the basic operations (in code) Provide your results below, and submit your code. Also, describe the pros and cons of your choice of performance metric Note: If you decide to use timing, the standard way to time an algorithm is to run the same problem 100...
Most questions answered within 3 hours.
-
The Bahraini public budget experiences deficit in the last
seven years, what are procedures are taken...
asked 58 seconds ago -
You invested $30,000 in a mutual fund at the beginning of the
year when the NAV...
asked 4 minutes ago -
Would you expect the price elasticity of supply for guitars to
be more inelastic in the...
asked 6 minutes ago -
A snowmobile is originally at the point with position vector
30.1 m at 95.0° counterclockwise from...
asked 6 minutes ago -
MAN3240 Organizational Behavior
In one to two paragraphs
6.) How can understanding emotions make me more...
asked 14 minutes ago -
Identify one individual who, in your opinion, is an excellent
leader. List the qualities that this...
asked 11 minutes ago -
For the data set shown below, complete parts (a) through (d)
below. x 3 4 5...
asked 17 minutes ago -
A university administrator working in student housing wants to
determine if the percentage of students residing...
asked 31 minutes ago -
3). Describe human population growth that has occurred in the
past 400 years. Use terms learned...
asked 28 minutes ago -
A
projectile is blue at a target. The distance from the point of
impact to the...
asked 53 minutes ago -
Given a 32 bit processor, with 2 MB of physical RAM split into 512
frames. What...
asked 43 minutes ago -
What were the main rulings in the Supreme Court cases which are
Morgan v. Virginia (1946)...
asked 42 minutes ago