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
- 3) For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in timet, assuming that the algorithm to solve the problem takes f (n) microseconds. 1 1 second minute hour day month year century lgn n n lg n n2 n3 2" п!arrow_forwardGiven 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_forwardAnother 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_forward
- I 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_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_forward7. 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_forward
- Problem FIG can be solved in O(RK + R log log n) time usingθ(R) space.Write Algorithm for itarrow_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
- Below 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_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_forwardHelp mearrow_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