Question

A program has runtime proportional to (log n)7 where n is the input size. Suppose we...

A program has runtime proportional to (log n)7 where n is the input size. Suppose we run the program with input size 10 and the runtime is 35 ms. What will the new  runtime be in seconds when we increase the input size to ten billion?.

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

Runtime of a program proportional to (logn)7 where n is the input size

considering base 10

Given Input Size n is 10 and Runtime is 35 ms

when we increase input n to 10 billion(1010)

We calculated Constant K=0.035 and Given input n=1010

When we increase the input to 10 billion run time is 350000 seconds

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Suppose the runtime of a computer program is proportional to n(logn)2. For input size 28 the...
Suppose the runtime of a computer program is proportional to n(logn)2. For input size 28 the runtime is 154 ms. What is the new runtime in ms when the input size is squared? (Type just the number, not "ms")
Suppose the runtime of a computer program is proportional to the fourth root of the input...
Suppose the runtime of a computer program is proportional to the fourth root of the input size. If the original runtime is 165 ms and the input size is multiplied by 8,598 what is the new runtime in ms? (Just type the number not "ms"). Round your answer to the nearest whole number.
A program takes time T(n) = k2n  where k is some constant and n is the input...
A program takes time T(n) = k2n  where k is some constant and n is the input size. The program is run twice on the same computer (so k is the same in both cases). The first run is with n = 4 and the time taken is 20 ms. The second run is with n = 10. What is the time taken for the second run, in milliseconds? (Type in just the number; don't type "ms" at the end.)
discrete structures problems 1. A program P takes time proportional to logn where n is the...
discrete structures problems 1. A program P takes time proportional to logn where n is the input size. If the program takes 1 minute to process input of size 1,000,000, how many seconds does it take to process input of size 100? 2. When the best possible algorithm to solve a problem is exponential-time, or in general in nonpolynomial (not in O(np) for any p) we call such a problem ___________________. 3. f(x) is O(x 2) and g(x) is O(x...
Given a DFA M with n states where the input alphabet has k characters, we can...
Given a DFA M with n states where the input alphabet has k characters, we can determine if the L(M) =empty set in time: A. n B. k C. n+k D. nk
Suppose that we take a random sample of size n from a population having a mean...
Suppose that we take a random sample of size n from a population having a mean μ and a standard deviation of σ. What is the probability or confidence we have that our sample will be within +/- 1 of the population mean μ? (a) μ = 10, σ = 2, n = 25
Suppose we have a random sample of size 50 from a N(μ,σ2) PDF. We wish to...
Suppose we have a random sample of size 50 from a N(μ,σ2) PDF. We wish to test H0: μ=10 versus H1: μ=10. The sample moments are x ̄ = 13.4508 and s2 = 65.8016. (a) Find the critical region C and test the null hypothesis at the 5% level. What is your decision? (b) What is the p-value for your decision? (c) What is a 95% confidence interval for μ?
Write a program (O(n), where n is the number of words) that takes as input a...
Write a program (O(n), where n is the number of words) that takes as input a set of words and returns groups of anagrams for those words. Complete your code here - For example, if the list is "debitcard", "elvis", "silent", "badcredit", "lives", "freedom", "listen", "levis", the output should be silent listen debitcard badcredit elvis lives levis Note that freedom has no anagram, and hence is not printed. ///////////////////////////////////////////////$%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% anagram.cpp #include <iostream> #include <unordered_map> #include <vector> #include <algorithm> using namespace...
Using VBA in excel, Consider a city like Manhattan where avenues run north-south and streets run...
Using VBA in excel, Consider a city like Manhattan where avenues run north-south and streets run east-west. Suppose it is a 7 x 10 grid, so there are 70 grid points each marked by an x coordinate and a y coordinate (from (0,0) to all the way to (6, 9). We are interested in the following question: if we locate a fire station at point (i, j), how many points can a truck sent from the station reach within 3...
1.Let f and g be two functions such that f(n)/g(n) converges to a positive value less...
1.Let f and g be two functions such that f(n)/g(n) converges to a positive value less than 1 as n tends to infinity. Which of the following is necessarily true? Select one: a. g(n)=Ω(f(n)) b. f(n)=Ω(g(n)) c. f(n)=O(g(n)) d. g(n)=O(f(n)) e. All of the answers 2. If T(n)=n+23 log(2n) where the base of the log is 2, then which of the following is true: Select one: a. T(n)=θ(n^2) b. T(n)=θ(n) c. T(n)=θ(n^3) d. T(n)=θ(3^n) 3. Let f and g be...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT