An algorithm takes 0.5 ms for input size of 100. How long will it take for...

Question

Question

An algorithm takes 0.5 ms for input size of 100. How long will it take for an input of size of 500 assuming a big-O runtime of:

a. O(? 2 )

b. O(? log10 ?)

Answer 1

Answer #1

a)

$t=\frac{n_1^2}{n_2^2}*t_2$

t= 5002 * 0.5 = 25 * 0.5 = 12.5 ms

Answer: 12.5 ms

b)

nalog 10 11 nalog 10 n2 to

500 log 10500 - *0.5 100 log 10 100

t = 5*1.35 * 0.5 = 3.375ms

Answer: 3.375 ms

Answer 2

Similar Homework Help Questions

For part (b), An algorithm takes 0.5 ms for input size 100. How large a problem...

For part (b), An algorithm takes 0.5 ms for input size 100. How large a problem can be solved in 1 min if the running time is the following (assume low-order terms are negligible): a. linear b. O(NlogN) c. quadratic d. cubic
Suppose that an algorithm takes 30 seconds for an input of 224 elements (with some particular,...

Suppose that an algorithm takes 30 seconds for an input of 224 elements (with some particular, but unspecified speed in instructions per second). Estimate how long the same algorithm, running on the same hardware, would take if the input contained 230 elements, and that the algorithm's complexity function is: Big theta not Big O a) Big theta(N) b) Big theta (log N) c) Big theta (N log N) d) Big theta(N^2) Assume that the low-order terms of the complexity functions...
Explain how to analyze an algorithm to determine its input size and its Big-O, Big Theta,...

Explain how to analyze an algorithm to determine its input size and its Big-O, Big Theta, and/or Big Omega.

(d) Consider an algorithm A, whose runtime is dependent on some "size" variable n of the...

(d) Consider an algorithm A, whose runtime is dependent on some "size" variable n of the input. Explain the difference between the two statements below, and give an explicit example of an algorithm for which one statement is true but the other is false. 1. The worst case time complexity of A is n2. 2. A is O(n). (e) Give an example of an algorithm (with a clear input type) which has a Big-Oh (0) and Big-Omega (12) bound on...
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 ?
(a) Design an algorithm that reveals some secret integer number from the set {1, 2, ......

(a) Design an algorithm that reveals some secret integer number from the set {1, 2, ... , n} by guessing random numbers within the given range until the secret number has been guessed. Numbers should be replaced after being guessed such that it is possible to guess 2 and then 2 again, assuming 2 is in the given range. The algorithm should return both the secret number as well as the number of guesses taken. (b) If possible, calculate the...

Which of the following answers is the least correct reason computer scientists perform algorithm analysis (i.e....

Which of the following answers is the least correct reason computer scientists perform algorithm analysis (i.e. Big-O classification)? To generate new solutions to a given problem. To see how the algorithm will perform when the input size gets bigger. To compare and contrast known solutions to a given problems. To analyse an algorithm's runtime complexity.
9. (5 points) Please describe an algorithm that takes as input a list of n integers...

9. (5 points) Please describe an algorithm that takes as input a list of n integers and finds the number of negative integers in the list. 10. (5 points) Please devise an algorithm that finds all modes. (Recall that a list of integers is nondecreasing if each term of the list is at least as large as the preceding term.) 11. (5 points) Please find the least integer n such that f() is 0(3") for each of these functions f()...
You are running algorithm with squared complexity on data with 100 elements and it takes 10...

You are running algorithm with squared complexity on data with 100 elements and it takes 10 seconds. How much time do you expect the algorithm will take when executed on data with 1000 elements? Order the following: O(n2), O(12 + 7n), O(n log(n) + 300 n2 + 1/125 n3)

A program with a quadratic run time takes t seconds to run, when given an input...

A program with a quadratic run time takes t seconds to run, when given an input size n. If the same algorithm is given input of size 2n, then the program will take approximately how many seconds? a. 2t b. t c. 4t d. 6t