In general, if an algorithm at each step divides the problem size by some constant c...
In general, if an algorithm at each step divides the problem size by some constant c > 1, so that at step 't' the problem size is only n / ct if n was the starting size, then such algorithm is said to have what kind of run - time?
Homework Answers
When we implement an algorithm in which the problem size (say ' n ') is divided by some constant c (c > 1) at each step then the number of steps in the program will decrease logarithmically.
For example, whenever we implement binary search algorithm for a sorted array of size n, at each step the size decreases to its half and rest half is neglected. If we have an array of size 10 and binary search is implemented then the size in each iteration will be 5,2,1 (reducing to its half ) and the number of iterations will be equal = log210 = 3.32 = 3 and thats the reason binary search has log n time complexity.
So, for an algorithm of size 'n' , if at each step the problem size is divided by some constant 'c' then the run - time will be = O ( logc (n) ).
Add Answer to:
In general, if an algorithm at each step divides the problem
size by some constant c...
Suppose the following is a divide-and-conquer algorithm for some problem. "Make the input of size n...
Suppose the following is a divide-and-conquer algorithm for some problem. "Make the input of size n into 3 subproblems of sizes n/2 , n/4 , n/8 , respectively with O(n) time; Recursively call on these subproblems; and then combine the results in O(n) time. The recursive call returns when the problems become of size 1 and the time in this case is constant." (a) Let T(n) denote the worst-case running time of this approach on the problem of size n....
An algorithm A executes some instructions to solve a problem of size n, the total number...
An algorithm A executes some instructions to solve a problem of size n, the total number of instruction is Θ (n3). An algorithm B executes half the instructions of A to solve the same problem of size n. What is the Big Theta of B (justify your answer) ?
LMS project Using the notes discussed in class: Implementing the LMS Algorithm First generate some signals clear all c...
LMS project Using the notes discussed in class: Implementing the LMS Algorithm First generate some signals clear all close al1: Generate signals for testing the LMS Algorithm 1000 Fs Sampling frequency Sample time 1/Fs 10000: = L Length of signal S Time vector (0:L-1) *T ; Sum of a 50 Hz sinusoid and a 120 Hz sinusoid 0.7 sin (2*pi*50*t); inuside X d+ 10 randn (size (t)); Sinusoids 5O0000000L plus noise fiqure (1) plot (Fs*t (1:150),x (1:1500)) title('Signal Corrupted with...
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...
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...
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...
1 2 3 The base case; reduce problem and general solution of the recursive algorithm of...
1
2
3
The base case; reduce problem and general solution of the recursive algorithm of n! are: O A. O! =0 (n-1)! n(n-1)! OB.O!= 1 (n-1)! n(n-1)! OC. O!=0 (n-1)! n(n-1) OD.0! = 1 (n-1) n(n-1) To set up the table for a party, if we use n tables and set up one next another as the picture. How many seats are there when if one side of the table can place only one chair? When determine Four-Step Methodology...
IOs, mltipncation, division) counts as one step of the algorithm. sheet, the ith problem is worth...
IOs, mltipncation, division) counts as one step of the algorithm. sheet, the ith problem is worth pi points. The problems must be solved in the given order, but it is possible to skip (not to solve) some of them. Furthermore, if a student solves the ith problem, then she/he gets so exhausted that she/he must skip the next fi problems (of course she/he may skip O(n) running time dynamic programming algorithm that determines the maximum possible points that are numbers...
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...
Problem 3 Suppose that you have a set of n large, orderable, objects, each of size...
Problem 3 Suppose that you have a set of n large, orderable, objects, each of size q, so that it requires time e(a) to time to compute a hash function h(a) for any object and requires time e(g) to compare any two objects. Describe a compound data structure, built out of a heap and a hash table, that supports the following operations with the specified run times.. elt (x) Is x an element of the set? Expected run time O(g)....
LMS project Using the notes discussed in class: Implementing the LMS Algorithm First generate some signals clear all close al1: Generate signals for testing the LMS Algorithm 1000 Fs Sampling frequency Sample time 1/Fs 10000: = L Length of signal S Time vector (0:L-1) *T ; Sum of a 50 Hz sinusoid and a 120 Hz sinusoid 0.7 sin (2*pi*50*t); inuside X d+ 10 randn (size (t)); Sinusoids 5O0000000L plus noise fiqure (1) plot (Fs*t (1:150),x (1:1500)) title('Signal Corrupted with...
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...
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...
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...
1
2
3
The base case; reduce problem and general solution of the recursive algorithm of n! are: O A. O! =0 (n-1)! n(n-1)! OB.O!= 1 (n-1)! n(n-1)! OC. O!=0 (n-1)! n(n-1) OD.0! = 1 (n-1) n(n-1) To set up the table for a party, if we use n tables and set up one next another as the picture. How many seats are there when if one side of the table can place only one chair? When determine Four-Step Methodology...
IOs, mltipncation, division) counts as one step of the algorithm. sheet, the ith problem is worth pi points. The problems must be solved in the given order, but it is possible to skip (not to solve) some of them. Furthermore, if a student solves the ith problem, then she/he gets so exhausted that she/he must skip the next fi problems (of course she/he may skip O(n) running time dynamic programming algorithm that determines the maximum possible points that are numbers...
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...
Problem 3 Suppose that you have a set of n large, orderable, objects, each of size q, so that it requires time e(a) to time to compute a hash function h(a) for any object and requires time e(g) to compare any two objects. Describe a compound data structure, built out of a heap and a hash table, that supports the following operations with the specified run times.. elt (x) Is x an element of the set? Expected run time O(g)....
Most questions answered within 3 hours.
-
An MNE is this kind of industry when competition in one country
is essentially independent of...
asked 1 hour ago -
. For this set of questions, determine what
proportion of a normal distribution is located betweeneach...
asked 1 hour ago -
A college student is employed as a door-to-door newspaper
salesman. Historical data suggests that the student...
asked 2 hours ago -
MATLAB HW 11 problem using Switch Case and Input commands
Write a script file that calculates...
asked 2 hours ago -
Considering gravitational time dilation, calculate the time that
passes in Earth’s surface while 1 hour passes...
asked 2 hours ago -
Minitab Problem: Take the Lake Hume June rainfall data and find
use the processes outlined in...
asked 3 hours ago -
X Company is trying to decide whether to continue using old
equipment to make Product A...
asked 3 hours ago -
IN PYTHON ONLY !! Program 2: Re-work
program #5 (WeeklyHours) from the previous assignment such that...
asked 4 hours ago -
The average length of time between arrivals at a turnpike
toll-booth is 26 seconds. What is...
asked 6 hours ago -
(a) A piston at 6.1 atm contains a gas that occupies a volume of
3.5 L....
asked 7 hours ago -
Please answer true or false. Words
cannot be changed or added in to make it true...
asked 7 hours ago -
An empty test tube weighs 15.923 grams. Then,
MgCl2•6H2O is added into the test tube. After...
asked 7 hours ago