Consider the following “justification” that the Fibonacci function, F(n) is O(n): Base case (n ≤ 2): F(1) = 1 and F(2) = 2.
Induction step (n > 2): Assume claim true for n′ < n. Consider n. F(n) = F(n − 2) + F(n − 1). By induction, F(n − 2) is O(n − 2) and F(n − 1) is O(n − 1). Then, F(n) is O((n − 2) + (n − 1)), by the identity presented in Exercise R-4.16.
Therefore, F(n) is O(n).
What is wrong with this “justification”?
Want to see the full answer?
Check out a sample textbook solutionChapter 4 Solutions
Data Structures and Algorithms in Java
Additional Engineering Textbook Solutions
Web Development and Design Foundations with HTML5 (8th Edition)
Database Concepts (8th Edition)
C How to Program (8th Edition)
C Programming Language
Computer Systems: A Programmer's Perspective (3rd Edition)
Differential Equations: Computing and Modeling (5th Edition), Edwards, Penney & Calvis
- 3. Prove by induction that T(n) = 2T (n/2) + cn is O(n logn).arrow_forward6. Prove: For all integers n, if n² is odd, then n is odd. Use a proof by contraposition, as in Lemma 1.1.arrow_forward7. For n 2 1, in how many out of the n! permutations T = (T(1), 7(2),..., 7 (n)) of the numbers {1, 2, ..., n} the value of 7(i) is either i – 1, or i, or i +1 for all 1 < i < n? Example: The permutation (21354) follows the rules while the permutation (21534) does not because 7(3) = 5. Hint: Find the answer for small n by checking all the permutations and then find the recursive formula depending on the possible values for 1(n).arrow_forward
- Proof the following statement by definition of big O and big theta: If f(n) = O(g(n)), then f(n) + g(n) = Θ(g(n)).arrow_forwardSolve the following recurrence equations by expanding the formulas (also called the 'iteration method' on slides). Specifically, you should get T(n) = O(f(n)) for a function f(n). You may assume that T(n) = O(1) for n = O(1). You should not use the Master Theorem. (a) T(n) = 2T (n/3) + 1. (b) T(n) = 7T(n/7) + n. (c) T(n) = T(n − 1) + 2.arrow_forward3arrow_forward
- Let S = {3n :neZ}.A recursive definition for the set S is: %3D Basis Step: 3 ES Recursive Step: If x E S then a +3 E S Prove by structural induction that for every x E S, x+x E S. Hint: Use the recursive definition of S to set up your proof by structural induction and use the definition S = {3n : n e Z*} in your proof. + Drag and drop an image or PDF file or click to browse...arrow_forwardA) Prove the following by induction, substitution, or by definition that 5n²- n +1 = O(n) Definition of Big Theta f(n) = © (g(n)) means there are positive constants c1, c2, and no, such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ no. B) If this is not Theta, what is it?arrow_forwardtrue or falsearrow_forward
- Consider this function:boolean freaky(n) {// PRE: n is a positive integer// POST: ???if n < 2: return falsex = 2while x < n { if n mod x == 0 return false x = x + 1}return true}(i) Find the postcondition of this function(ii) Find the best possible big-oh bound for its complexity(iii) What can we say about big-thetacomplexity for this function?arrow_forwardPlease show steps clearlyarrow_forward3. I: II T(n) = 27)+n², then T(n) = O(nlogn). II: If T(n) = ! 27()+nlogn, then T(n) = O(nlogn). III: If T(n) = 2T(√) + logn, then T(n) = O(logn log n). (A) Only I is TRUE. (B) Only II is TRUE. (C) Only III is TRUE. (D)All of LII and III are TRUE. 4. (a) 5%Show that the lower bound for the sorting problem is (nlogn). (b) 3% The least signifcant digit first RadixSort sorts n numbers in O(n) and it beats the (nlogn) lower bound. What went wrong? (c) 5% Prove correctness of the O(n) time least significant digit first RadixSort. (d) 4% Show that finding the convex hull of n points in 2D space needs at least (nlogn) time. (e) 3% Show that finding the convex hull of n points in 3D spaceneeds at least (nlogn) time.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