Computer Science: An Overview (13th Edition) (What's New in Computer Science)
13th Edition
ISBN: 9780134875460
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
2. For a problem we have come up with three algorithms: A, B, and C. Running time
of Algorithm A is O(n¹000), Algorithm B runs in 0(2¹) and Algorithm C runs in
O(n!). How do these algorithms compare in terms of speed, for large input?
Explain why.
A computer science student designed two candidate algorithms for a problem while working
on his part-time job The time complexity of these two algorithms are
T,(n) = 3 n logn and T2(n) = n6/5
a) Which algorithm is better? Why?
b) If we run both algorithms at the same time with an input size of 105, which algorithm
produces results faster than the other one? Why?
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?
Chapter 12 Solutions
Computer Science: An Overview (13th Edition) (What's New in Computer Science)
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
- Given a program designed to calculate rocket trajectories, the algorithm has an O(2n) complexity and takes 1 second for each iteration, and n = 15. How many hours will it take to calculate the trajectories, worst case?arrow_forwardSuppose 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.arrow_forward2) A computer science student designed two candidate algorithms for a problem while working on his part-time job The time complexity of these two algorithms are T1(n) = 3 n logn and T2(n) = nº/5 . a) Which algorithm is better? Why? b) If we run both algorithms at the same time with an input size of 10°, which algorithm produces results faster than the other one? Why?arrow_forward
- Consider two algorithms for the same problem: • Algorithm A, which runs in O(n) and produces a correct answer with probability 0.7, and a wrong answer with probability 0.3. • Algorithm B, which runs in O(n log n) and produces a correct answer with probability 0.99, and a wrong answer with probability 0.01. Which of the two algorithms should you use to build a more asymptotically (in n) efficient algorithm with probability 0.99 of producing a correct answer? Justify. Assume that you can always check if an answer is correct in constant time.arrow_forwardIf 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_forwardAlgorithm A and Algorithm B have the same complexity. With an input of size 10 (i.e. n=10) and when executed on the same system, Algorithm A takes 5 seconds to execute and Algorithm B takes 10 seconds to execute. How much time does each take to execute if the input size is n=20? Select one: O a. Algorithm A takes 50 seconds, Algorithm B takes 55 seconds. b. Not enough information is given. OC Algorithm A takes 5 seconds, Algorithm B takes 10 seconds. Od. Algorithm A takes 10 seconds, Algorithm B takes 20 seconds.arrow_forward
- A certain computer algorithm executes twice as many operations when it is run with an input of size k as when it is run with an input of size k – 1 (where k is an integer that is greater than 1). When the algorithm is run with an input of size 1, it executes seven operations. How many operations does it execute when it is run with an input of size 26? For each integer n 2 1, let s, -1 be the number of operations the algorithm executes when it is run with an input of size n. Then s, = and s = for each integer k 2 1. Therefore, So, S1, S21 -Select--- with constant Select--- |, which is So, for every integer n 2 0, s, It follows that for an input of size 26, the number of ... is operations executed by the algorithm is s which equals ---Select--- varrow_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_forwardThis problem compares the running times of the following two algorithms for multiplying:algorithm KindergartenAdd(a, b) pre-cond: a and b are integers. post-cond: Outputs a × b.arrow_forward
- There 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_forwardA certain computer algorithm executes twice as many operations when it is run with an input of size k as when it is run with an input of size k - 1 (where k is an integer that is greater than 1). When the algorithm is run with an input of size 1, it executes seven operations. How many operations does it execute when it is run with an input of size 24? For each integernz 1, let s,-1 be the number of operations the algorithm executes when it is run with an input of size n. Then for each integer 2 1. Therefore, So, S3. Sz. is -Select- and s,= with constant Select- ,which is . So, for every integer n 2 0, s, = It follows that for an input of size 24, the number of operations executed by the algorithm is s -Select-v which equals Need Heln? Desdarrow_forwardYou are given a collection of n bolts of different widths and n corresponding nuts. You are allowed to try a nut and bolt together, from which you can determine whether the nut is larger than the bolt, smaller than the bolt, or matches the bolt exactly. However, there is no way to compare two nuts together or two bolts together. The problem is to match each bolt to each nut. Design an algorithm for this problem with Θ(n log n) average-case complexity (in terms of nut-bolt comparisons). Explain why your algorithm has Θ(n log n) average case complexity.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