2. [3] A program takes 10 seconds for input size 500 (i.e., n=500). Ignoring the effect of constants, approximately how much time can the same program be expected to take if the input size is increased to 2000 given the following run-time complexities? 1. O(N) 2. O(N log N) 3. O(N³)

2. [3] A program takes 10 seconds for input size 500 (i.e., n=500). Ignoring the effect of constants, approximately how much time can the same program be expected to take if the input size is increased to 2000 given the following run-time complexities? 1. O(N) 2. O(N log N) 3. O(N³)

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Q: Consider two programs-A and B that have the following performances: A. O(log n) B. O(n2) If each…

Q: For the following block of code, select the most appropriate run-time formula in terms of primitive…

A: Given Data:-

Q: Question 41 Given the problem of basic multiplication: Input: Two n-digit nonnegative integers, x…

A: Time Complexity: Overall effectiveness of any multiplication or addition can be determined by its…

Q: Assume that function f is in the complexity classO(N(Log_2 N)^3), and that for N = 1,000,000 the…

A: Given , function f = O(N(Log_2 N)^3) N = 1,000,000 T = 80 for (2) , N = 1,000,000,000

Q: Write a program to read the two variables x, y and calculate and print the value of D from the…

A: def Afun(X): A = X*2 + 4*X*3-2 return A def Bfun(X,Y): B = Y*7 + 5*X + 3 return B…

Q: Find the minimum number of platforms in a train station to avoid delays in the arrival of a train.…

A: Given Data, We have to find the minimum number of platforms in a train station to avoid delays in…

Q: for i in range(n): Fa() for i in range(1+1): ACE CC for k in range(n): Fa() Fb()Intermal ONLY a)…

Q: Suppose you are given n machines M1, . . . , Mn and n jobs J1, . . . , Jn. Each machine is designed…

A: Introduction Suppose you are given n machines M1, . . . , Mn and n jobs J1, . . . , Jn. Each machine…

Q: 4.If the efficiency of the algorithm dolt can be expressed as O(n) = n2, calculate the efficiency of…

A: Given :

Q: Problem 3. Let n be an integer. Write dynamic programming algorithm which determines in how many…

A: Dynamic programming Dynamic programming is mostly an enhancement over simple recursion. Dynamic…

Q: Q4 (a) Identify the work done, f F. dr by an electric field, E = (x + xy)i + (y + 5)j - 5zk +2²= V/m…

Q: Develop a python program for the following problem statement: There are N frogs (numbered 1 through…

A: As per the given problem statement we have to develop python code to is to sort the frogs in the…

Q: (25 p) Problem 2. Consider the following algorithm including 8 steps. S1: START S2: INPUT A, B S3: T…

A: EXPLANATION: This algorithm contains two variable. Firstly it takes the value of both the variables…

Q: Coding Language is Python, keep it as simple as possible thanks. N one dimensional kingdoms are…

A: Algorithm: 1. Take the input from the user 2. Run the code for all test cases 3. Apply the condition…

Q: For each function f(n) and timet in the following table, determine the largest size n of a problem…

A: Answer: I have given answer in the brief explanation.

Q: # Solve it with C programing On a bus, there are N number of passengers sitting on their seats…

A: The program is based on the arrays hence declare an array of size N. Initially, read size of the…

Q: Let us assume x = [1:4]; The result of operation y = x' will give O Error O [1,2,3,4] O [1;2;3;4] O…

A: Y is a column vector. Thus y will become y = 1 2 3 4

Q: Design a reasonably efficient algorithm for solving each of the following problems and determine its…

A: AlgorithmLet x be one of the numbers and the other number is n-x. The first step is to maximize f(x)…

Q: f ( i% =

A: GIVEN CODE for(int i=0;i<n;i++){ if(i%2==0) i=n; else i--; }…

Q: 5. Given the following algorithm, and assuming Fi(10,2, x=350 y=5 for i=1 to 10 x=x+y print x (a)…

A: Given :- The following algorithm, and assuming Fl(10,2,-10,10)x=350y=5for i=1 to 10 x=x+yprint x (a)…

Q: 3. Show the output that would be generated by each of the following program fragments: a) for ch in…

A: a) for ch in "aardvark": print(ch) Output : - a a r d v a r k b) for w in "Now is the winter of…

Q: Coding Language is Python, keep it as simple as possible thanks. N one dimensional kingdoms are…

A: ExplanationThere are three kingdoms [1,3] ,[2,5] and [6,9]. You will need at least 2 bombs to…

Q: can someone explain the logic of these problems 1A.Which of the following is illegal in C? (2 is…

A: Note: This is a multiple-question-based problem. As per company guidelines, only the first question…

Q: George creates a test algorithm to calculate the growth rate for a particular function. George uses…

A: To Do: To choose the correct option.

Q: Answer in C++, show example output please There are three buckets size X, Y, M (1<=X<=Y<=M). All…

A: Answer is given below-

Q: 4. Use the equality proven in question 3 to design an algorithm to compute the nth Fibonacci number…

A: Answer: I have done code and also I have attached code code screenshot as well as output in C++…

Q: a) Assume that five generation units with third order cost function (F: (P) = A₂ P²³ + B; P; ² + C;…

A: The complete answer in python programming language is below:

Q: PROBLEM 24 – 0580: spontaneously disintegrates at a rate Radioactive material that depends on the…

A: The amount of material that remains is a result of past disintegration, and the present decay rate…

Q: 17. Solve the following system of equations. x-2y 5 -3x + 2y = 7 O A.x=-6, y = -1/2 O B. x = 3, y =…

A: Here in this question we have have given two linear equations and we have asked to solve these…

Q: 1.) If f(x) = 2.x^2 - x + 5. What is f(-3)? 2.) If A = {a, b, d, e}, B = {b, c, e, f} and C = {d,…

Q: Q1: Write a MATLAB program to Solve the following system of three linear equations: 2x + 3y = 0.5…

A: (sorry dear ! As per Bartleby guidelines we are supposed to answer only first question from a given…

Q: Computer Science Code the below in python or C: Given: n*m bar of chocolate and minimum number of…

A: def findMinimum(arr, n, k): res = 0 i = 0…

Q: Coding Language is Python, keep it as simple as possible thanks. N one dimensional kingdoms are…

A: Algorithm: 1. Take the input from the user 2. Run the code for all test cases 3. Apply the condition…

Q: Q15: Analyze the time complexity of the below powering code. This code shows the divide and conquer…

A: Maters theorem is used to find out the time complexity of the recursive programs if the recurrence…

Q: (a) Cônsider the following algorithm segment. for i := 1 to8 for j:= 1 to i [Statements in body of…

A: Given algorithm is: for i : 1 to 8 for j : 1 to i [Statements in body of inner loop,…

Q: For each function fln) and time t in the following table, determine the largest size n of a problem…

A: Check further details for the answers :

Q: 1.10 Mathematically, do you expect the rms error to change with N? Do the results of your program…

A: Below i have answered:

Q: Q1/ for the matrix a(/3,3/) and the program below, the outputs are: do i=1,3 do j=1,3 if (ij) then…

A: I have used python in solving for the output.

Q: (b) Given T(n) = 817(n/3) + d, 3 ≤ d ≤ 27, use the Master Theorem to determine its asymptotic…

A: The master theorem finds the time complexity of the algorithm is represented in the form of the…

Q: Suppose that you implement an algorithm to solve a problem. It works correctly and quickly for small…

A: Please find the answer below :

Q: Q1) Write a Matlab program to read the value of (x) then compute and print the value of the…

A: Start Input value of x For 8 times, add term to w Print value of w Stop

Q: Suppose you are given n machines M1, . . . , Mn and n jobs J1, . . . , Jn. Each machine is designed…

A: Given a set J of jobs, |J| = n, a set M of machines, |M| = m, and for each j ∈ J and i ∈ M, the time…

Q: (b) The function, FIRST: {0, 1}* {0, 1} which outputs 1 if the first bit of the input is a 1 and…

A: given, FIRST:{0,1}*->{0,1} it outputs 1 if the first bit of the input is a 1 and outputs 0…

Q: 5. When a resistor (R), capacitor (C) and battery (V) are connected in series, a charge Q builds up…

Q: 3. Construct a Python program that implements the following: a. Suppose that a problem has an exact…

Q: In this problem you will need to use complex number arithmetic. Assume that the equation f(x) = 0…

A: import math def func_e_to_2(n): x = 2 e_to_2 = 0 for i in range(n): e_to_2 +=…

Q: 1. Consider a three-dimensional coordinate system in which a dart is projected at position (x0, Yo,…

Concept explainers

Computational Systems

The computation systems can be defined as the systems that are capable of solving a problem that includes calculations either mathematical or logical, and are able to produce the result as an output. For example, a simple calculator that is given a set of numbers and operators as input and produces the result as an output can be defined as a computational system. The above example is a simple illustration only, the computational systems range from simple devices to complex devices such as the systems that control the SpaceX companies, Starlink satellites which are being quite recently seen in the skies at many places globally.

Question

2. [3] A program takes 10 seconds for input size 500 (i.e., n=500). Ignoring
the effect of constants, approximately how much time can the same program be
expected to take if the input size is increased to 2000 given the following
run-time complexities?
1. O(N)
2. O(N log N)
3. O(N³)

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Step 1

VIEW

Step 2

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

Consider two programs-A and B that have the following performances: A. O(log n) B. O(n2) If each program requires 7 seconds to solve a problem of size 100, estimate the time required by each program for a problem of size 200. [log 100 = 6.64]
Mathematics is a very crucial subject in our life. It gives a power to calculate the daily things. Rajesh is the one of the brightest student in this subject so he has an integer N. His task is to break N into some number of (integer) powers of 2. TO achieve this, he can perform the following operation several times (possibly, zero): Choose an integer X which he already has, and break X into 2 integer parts (Y and Z) such that X = Y + Z. Find the minimum number of operations required by Rajesh to accomplish his task using Python Language. Input 1 3 Output 1
The power function can be defined as follows: What is the worst-case running time complexity of this function? Select one: a. O(n2)O(n2) b. O(n)O(n) c. O(n−−√)O(n) d. O(logn)
Using Ackermann’s Function to check how slowly a program can run, Implement the algorithm. Assume the input parameters n and k are natural numbers.
Suppose the runtime efficiency of an algorithm is presented by the function f(n) = 10n + 10². Which of the following statements are true? Indicate every statement that is true. A. The algorithm is O(n log n) B. The algorithm is O(n) and O(log n). C. The algorithm is O(log n) and 80(n). D. The algorithm is (n) and (log n). E. All the options above are false.
Prove that the following algorithmfor the multiplication of natural numbers is correct, for all integer constants c ≥ 2. function multiply(y, z) comment Return yz, where y, z ∈ IN 1. x := 0; 2. while z > 0 do 3. x := x + y · (z mod c); 4. y := c · y; z := z/c ; 5. return(x)
2. (a) Consider the following algorithm. Input: A non-negative integer n. (1) If n % 5 = 0, stop. Otherwise, go to (2). (2) Replace n by n +3, and go back to (1). Prove that this algorithm terminates for every choice of the input n. (b) Consider the following algorithm, in which f(n) = n – 7n² + 14n – 8. Input: An integer n. (1) If f(n) = 0, stop. Otherwise, go to (2). (2) Replace n by n² % 7 and go back to (1). Prove that this algorithm terminates if and only if n is not a multiple of 7.
I am stuck on this Problem.. Theory Of Computation.. Write pseudocode for an algorithm relies on R to find the lowest cost ticket. You may assume that $0 is the lowest possible price.
In Big-Θ notation, analyze the running time of the following piece of code/pseudo-code. Describe the running time as a function of the input size (here, n). You should always explain your work when solving mathematics problems.
\Question No.2 Find f(1), f(2), S (3), and f(4) if s(n) is defined recur- sively by f(0) = 1 and for n 0, 1, 2, ... a) S(n + 1) = f(n) + 2. b) f(n + 1) -3/ (п). c) f(n + 1) = 2/W). d) S(n + 1) = (n)2 + S(n) + 1. Find f(1), f(2), f (3), f (4), and f (5) if f (n) is defined recursively by f (0) = 3 and for n =0, 1, 2, ... a) f(n + 1) = -2 (n). b) f (n + 1) = 3/ (n) +7. c) f(n + 1) = / (n)2 - 25 (n) – 2. d) f(n + 1) = 3/(m)/3. %3D Find f (2), f(3), f(4), and f(5) if f is defined recur- sively by f(0) =-1, S(1) = 2, and for n= 1, 2, ... a) f(n + 1) = S(n) + 35 (n – 1). b) f(n + 1) = f (n)?f (n – 1). c) f(n + 1) = 3/ (n)2 – 4f (n - 1)2. d) f (n + 1) = (n - 1)/S(n). Find f(2), S(3), (4), and f(5) if f is defined recur- sively by f(0) = (1) 1 and for n= 1, 2, ... a) S(n + 1) = f (n) - S(n – 1). b) f (n + 1) = f (n)/ (n - 1). c) f(n + 1) = / (n)2 + S(n – 1). d) f(n + 1) = r (n)/S(n - 1).
Suppose that f (n) = 0(g(n)) and f(n) = 0(h(n)), then it is ( always / sometimes / never ) the case that g(n) = 0(h(n)).
Q.No.2. Consider 3 , 5 , 8 , 10 , 5 , 2 , 1 ,7, 3 , 13 as an input to the list of n integers. Dry run the following piece of code and find out the answer. procedure func(al, a2, ..., an: integers) k:= 0 for i:= 1 to n if i is odd then k: = k+ai+i return k