Question

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 3) then we know f(x) + g(x) is O(x r). What is the smallest integer value of r for which this is true?

Math   Advanced-Math   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

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
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm that is executed most frequently. Express the number of times it is executed as a function of N. Convert this expression into the Big-O notation. A. For each of the three fragments of code, what is its worst-case time complexity, in the form "O(…)". (Use the given solution to the first problem as a model)                 //----------------- This is a sample problem – solved ------...
Problem 1: Relations among Useful Discrete Probability Distributions. A Bernoulli experiment consists of only one trial...
Problem 1: Relations among Useful Discrete Probability Distributions. A Bernoulli experiment consists of only one trial with two outcomes (success/failure) with probability of success p. The Bernoulli distribution is P (X = k) = pkq1-k, k=0,1 The sum of n independent Bernoulli trials forms a binomial experiment with parameters n and p. The binomial probability distribution provides a simple, easy-to-compute approximation with reasonable accuracy to hypergeometric distribution with parameters N, M and n when n/N is less than or equal...
I. Solve the following problem: For the following data: 1, 1, 2, 2, 3, 3, 3,...
I. Solve the following problem: For the following data: 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 6 n = 12 b) Calculate 1) the average or average 2) quartile-1 3) quartile-2 or medium 4) quartile-3 5) Draw box diagram (Box & Wisker) II. PROBABILITY 1. Answer the questions using the following contingency table, which collects the results of a study to 400 customers of a store where you want to analyze the payment method. _______B__________BC_____ A...
Consider the C program (twoupdate) to demonstrate race condition. In this assignment, we will implement Peterson's...
Consider the C program (twoupdate) to demonstrate race condition. In this assignment, we will implement Peterson's algorithm to ensure mutual exclusion in the respective critical sections of the two processes, and thereby eliminate the race condition. In order to implement Peterson's Algorithm, the two processes should share a boolean array calledflagwith two components and an integer variable called turn, all initialized suitably. We will create and access these shared variables using UNIX system calls relating to shared memory – shmget,...
Hi, I'm writing a Java program that prints a grid with circles and squares that have...
Hi, I'm writing a Java program that prints a grid with circles and squares that have letters in them and it is also supposed to print the toString() function to the console window each time the application runs. This toString() function is supposed to show the tile's shape, letter, and color component (or components). Could someone please review and debug my code to help me figure out why my toString() function is not working? import javax.swing.JFrame; import javax.swing.JPanel; import javax.swing.JButton;...
I NEED TASK 3 ONLY TASK 1 country.py class Country:     def __init__(self, name, pop, area, continent):...
I NEED TASK 3 ONLY TASK 1 country.py class Country:     def __init__(self, name, pop, area, continent):         self.name = name         self.pop = pop         self.area = area         self.continent = continent     def getName(self):         return self.name     def getPopulation(self):         return self.pop     def getArea(self):         return self.area     def getContinent(self):         return self.continent     def setPopulation(self, pop):         self.pop = pop     def setArea(self, area):         self.area = area     def setContinent(self, continent):         self.continent = continent     def __repr__(self):         return (f'{self.name} (pop:{self.pop}, size: {self.area}) in {self.continent} ') TASK 2 Python Program: File: catalogue.py from Country...
Please answer the following Case analysis questions 1-How is New Balance performing compared to its primary...
Please answer the following Case analysis questions 1-How is New Balance performing compared to its primary rivals? How will the acquisition of Reebok by Adidas impact the structure of the athletic shoe industry? Is this likely to be favorable or unfavorable for New Balance? 2- What issues does New Balance management need to address? 3-What recommendations would you make to New Balance Management? What does New Balance need to do to continue to be successful? Should management continue to invest...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT