To complete the table for given function
Explanation of Solution
Given Information:The time taken by
Explanation:
Since 1 microsecond is equal to
Consider the function
as follows:
Therefore, the value of
Since 1 hour is equal to 3600 seconds. Therefore, 1 hour is equal to
Again, consider the function
as follows:
Therefore, the value of
Consider a month is equal to 30 days and a year is equal to 365 days.
Similarly, calculate the other values of
Complete the table for different values of
as follows:
1 second | 1 minute | 1 hour | 1 day | 1 month | 1 year | 1 century | |
62746 | 2801417 | 133378058 | 2755147513 | 71870856404 | 797633893349 | ||
1000 | 7745 | 60000 | 293938 | 1609968 | 5615692 | 56176151 | |
100 | 391 | 1532 | 4420 | 13736 | 31593 | 146679 | |
19 | 25 | 31 | 36 | 41 | 44 | 51 | |
9 | 11 | 12 | 13 | 15 | 16 | 17 |
Table 1
Want to see more full solutions like this?
Chapter 1 Solutions
Introduction to Algorithms
- Given an n-element array X of integers, Algorithm A executes an O(n) time computation for each even number in X and an O(log-n) time computation for each odd number in X. What are the best case and worst case for running time of algorithm C?arrow_forwardFind the relation between the following functions: f(n) = log n and g(n) = Vn. (Square root for n)Hint: you may use L'Hopital's Theorem. For 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. Suppose you have algorithms with the two running times listed below. Suppose you have a computer that can perform 6 operations per second, and you need to compute a result in at most an hour of computation. For each of the algorithms, what is the largest input size n for which you would be able toget the result within an hour for:a) n^3b)10n^2arrow_forwardI have two functions in a function, one has a time complexity of O(n) and the other one has a time complexity of O(n^2). what is the overall time complexity of the function? def function(): def function1(): def function2():arrow_forward
- Another recursive algorithm is applied to some data A = (a₁, ..., am) where m = 2* (i.e. 2, 4, 8,16 ...) where x is an integer ≥ 1. The running time T is characterised using the following recurrence equations: T(1) = c when the size of A is 1 T(m) = 2T (2) + c otherwise Determine the running time complexity of this algorithm.arrow_forwardConsider array A of n numbers. We want to design a dynamic programming algorithm to find the maximum sum of consecutive numbers with at least one number. Clearly, if all numbers are positive, the maximum will be the sum of all the numbers. On the other hand, if all of them are negative, the maximum will be the largest negative number. The complexity of your dynamic programming algorithm must be O(n2). However, the running time of the most efficient algorithm is O(n). Design the most efficient algorithm you can and answer the following questions based on it. To get the full points you should design the O(n) algorithm. However, if you cannot do that, still answer the following questions based on your algorithm and you will get partial credit. Write the recursion that computes the optimal solution recursively based on the solu- (a) tion(s) to subproblem(s). Briefly explain how it computes the solution. Do not forget the base case(s) of your recursion.arrow_forwardProblem FIG can be solved in O(RK + R log log n) time usingθ(R) space.Write Algorithm for itarrow_forward
- 7. Suppose that you have two different algorithms for solving a problem. To solve a problem of size n, the first algorithm uses exactly n(log2 n) operations and the second algorithm uses exactly n3/2 operations. As n grows, which algorithm uses fewer operations?arrow_forwardFor 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?arrow_forwardA 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?arrow_forward
- 2) 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_forwardAn algorithm A, has a runtime T1(n) defined (in seconds) by the following function:- T1(n) = n? +n +50 For n = 9, the runtime of algorithm A, is 140 seconds. Runtime of another algorithm A, is represented by the following equation:- T2(n) = 2n³ + 14n + 230 For n = 2, the runtime of algorithm Az is 274 seconds. Algorithm Az with runtime represented by the following equation. T3(n) = 3n? + 33n + 333 Identify all values of n (if such values exist) for which the runtime of Az exceeds the given runtime of 140 sec of A, but is less than the runtime of 274 seconds of A2. Type your answer here.arrow_forwardBelow is a list of functions that commonly appear in complexity analyzes as a function of the size n of the problem. Sort the functions in ascending order of growth rate, that is, the slowest growing one is 1, and so on. Note that the functions are described in the notation O(.), which represents the cost of the algorithm as a function of the predominant term of the cost expression.arrow_forward
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education