Computer Science: An Overview (12th Edition)
12th Edition
ISBN: 9780133760064
Author: Glenn Brookshear, Dennis Brylow
Publisher: PEARSON
expand_more
expand_more
format_list_bulleted
Question
Chapter 12, Problem 40CRP
Program Plan Intro
It is defined as the rate at which the algorithm performs, that is slow or fast.
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solution
Students have asked these similar questions
Let us assume that we have two algorithms A and B. Algorithm A has run time given by (10n)2 and algorithm B has run time given by (Sin2n + Cos2n +1)n where n is the input size. Also assume that both algorithms are run on the same computer. Find the smallest value of n for which the runtime of algorithm A is less than the run time of algorithm B.
For a given problem with inputs of size n, algorithms running time,one of the algorithm is o(n), one o(nlogn) and one o(n2). Some measured running times of these algorithm are given below:
Identify which algorithm is which and explain the observed running Times which algorithm would you select for different value of n?
Suppose that the running time of an algorithm A is T(n) = n2. If the time it takes for algorithm A to finish on an input of size n 10 is 100ms, what will be the time that it will take for A to finish on an input of size 20? Assume that the algorithm runs on the same machine.
Chapter 12 Solutions
Computer Science: An Overview (12th Edition)
Ch. 12.1 - Prob. 1QECh. 12.1 - Prob. 2QECh. 12.1 - Prob. 3QECh. 12.1 - Prob. 4QECh. 12.2 - Prob. 1QECh. 12.2 - Prob. 2QECh. 12.2 - Prob. 3QECh. 12.2 - Prob. 4QECh. 12.2 - Prob. 5QECh. 12.3 - Prob. 1QE
Ch. 12.3 - Prob. 3QECh. 12.3 - Prob. 5QECh. 12.3 - Prob. 6QECh. 12.4 - Prob. 1QECh. 12.4 - Prob. 2QECh. 12.4 - Prob. 3QECh. 12.5 - Prob. 1QECh. 12.5 - Prob. 2QECh. 12.5 - Prob. 4QECh. 12.5 - Prob. 5QECh. 12.6 - Prob. 1QECh. 12.6 - Prob. 2QECh. 12.6 - Prob. 3QECh. 12.6 - Prob. 4QECh. 12 - Prob. 1CRPCh. 12 - Prob. 2CRPCh. 12 - Prob. 3CRPCh. 12 - In each of the following cases, write a program...Ch. 12 - Prob. 5CRPCh. 12 - Describe the function computed by the following...Ch. 12 - Describe the function computed by the following...Ch. 12 - Write a Bare Bones program that computes the...Ch. 12 - Prob. 9CRPCh. 12 - In this chapter we saw how the statement copy...Ch. 12 - Prob. 11CRPCh. 12 - Prob. 12CRPCh. 12 - Prob. 13CRPCh. 12 - Prob. 14CRPCh. 12 - Prob. 15CRPCh. 12 - Prob. 16CRPCh. 12 - Prob. 17CRPCh. 12 - Prob. 18CRPCh. 12 - Prob. 19CRPCh. 12 - Analyze the validity of the following pair of...Ch. 12 - Analyze the validity of the statement The cook on...Ch. 12 - Suppose you were in a country where each person...Ch. 12 - Prob. 23CRPCh. 12 - Prob. 24CRPCh. 12 - Suppose you needed to find out if anyone in a...Ch. 12 - Prob. 26CRPCh. 12 - Prob. 27CRPCh. 12 - Prob. 28CRPCh. 12 - Prob. 29CRPCh. 12 - Prob. 30CRPCh. 12 - Prob. 31CRPCh. 12 - Suppose a lottery is based on correctly picking...Ch. 12 - Is the following algorithm deterministic? Explain...Ch. 12 - Prob. 34CRPCh. 12 - Prob. 35CRPCh. 12 - Does the following algorithm have a polynomial or...Ch. 12 - Prob. 37CRPCh. 12 - Summarize the distinction between stating that a...Ch. 12 - Prob. 39CRPCh. 12 - Prob. 40CRPCh. 12 - Prob. 41CRPCh. 12 - Prob. 42CRPCh. 12 - Prob. 43CRPCh. 12 - Prob. 44CRPCh. 12 - Prob. 46CRPCh. 12 - Prob. 48CRPCh. 12 - Prob. 49CRPCh. 12 - Prob. 50CRPCh. 12 - Prob. 51CRPCh. 12 - Prob. 52CRPCh. 12 - Prob. 1SICh. 12 - Prob. 2SICh. 12 - Prob. 3SICh. 12 - Prob. 4SICh. 12 - Prob. 5SICh. 12 - Prob. 6SICh. 12 - Prob. 7SICh. 12 - Prob. 8SI
Knowledge Booster
Similar questions
- If algorithm A has running time 2n3 + 2n2 + 5 and algorithm B has running time 2n2, then: Select one: A.Algorithm B is asymptotically greater B.Algorithm A is asymptotically greater C.Both have the same asymptotic time complexity D.Both Algorithms will be of Quadratic complexityarrow_forwardThere are 3 algorithms to solve the same problem. Let n = problem size. Suppose that their runtime complexities are as follows: Runtime complexity of algorithm 1: T₁ (n) 2 Σ₁k² +logn³ +4 k=1 Runtime complexity of algorithm 2: T₂(n) 8n² + 2n+n√n Runtime complexity of algorithm 3: T3(n) = n logn + log4 nª + 64n Find asymptotic tight bound (Big-✪) of each runtime complexity, e.g. write T₁(n) = ☺(...). Which algorithm's runtime has the biggest growth rate, and which one has the smallest growth rate? Which algorithm is the most runtime efficient? = lognarrow_forwardSuppose you have algorithms with five running times. Assume these are the exact running times. How much slower do each of these algorithms get when you (a) double the input or (b) increase the input size by one? Do both. This problem requires discrete math. I solved all of these but I had a quick question. My teacher wanted us to use the big 0 notation for these running times, but the problem is that I'm not sure if that's necessary for these problems for the question it's asking. I tried to the big 0 notations for the first three. For (a) I got 8n3. Which I'm not sure is right. For example, for 1b I got 3n2 + 3n + 1 for how much slower these get from the original. Is that correct? Was I supposed to do something more for the big 0 notation. You can check to see if these answers are correct. The big O notation formula is f(n) = 0(g(n)). (a) n2 For double size I got 4n2. I got 2n + 1 from the input the size by one. I think that's all I need to do. I got similar answers for theother…arrow_forward
- please answer with proper explanation and step by step solution.arrow_forwardAn algorithm takes 0.5ms for input size 100. How long will it take for input size 500 (assuming thatthe lower-order terms are negligible) if the running time of the algorithm is O(1)? What is algorithm is O(n)?arrow_forwardGiven an algorithm has quadratic performance and has a runtime of 3 minutes for 1000 inputs, am I right in saying I can expect a 3 million minute runtime for 100,000 inputs ? Quadratic performance is O(n^2)arrow_forward
- When the order of growth of the running time of an algorithm is N log N, the doubling test will lead to the hypothesis that the running time is ~ a N for a constant a. Isn’tthat a problem?arrow_forwardSuppose three algorithms A, B, and C, can be implemented to perform a task. The algorithms have the following time complexities: A~0(n), B~0(n²), C~ 0(log2(n)). If the task runs an average input of size 100, rank the algorithms from least time- complex to most-time complex. Explain your choice.arrow_forwardGiven n> 3 points P1 = (X1, y1), ..., Pn = (Xn, Yn) in the coordinate plane, design an algorithm to check whether all the points lie within a triangle with its vertices at three of the points given. You can either design an algorithm from scratch or transform the problem to another one with a known algorithm. %3Darrow_forward
- Two algorithms A, B sort the same problem. When you go through each algorithm and break them down into their primitive operations, each can be represented as below A = n4 + 100n2 + 10n + 50 B = 10n3 + 2n2 + nlogn + 200 For very large values of n which of these algorithms explain why B will run in the shortest time to solve the problemarrow_forwardFor function f(n)=log n and time t=1 second, determine the largest size n of a problem that can be solved in time t, assume that the algorithm to solve the problem takes f(n) microseconds.arrow_forwardThe travel time function of an algorithm has the form: f(n) = 3n^2 + 4n + 8 Prove that Big Oh is n^2 which is denoted by f(n) = O(n^2);arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill Education
Starting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSON
Digital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSON
Database Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage Learning
Programmable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education