a) You are given two different codes for finding the n-th Fibonacci number. Find the time complexity of both implementations and compare the two. Implementation 1 def fibonacci_1 (n) : if n < 0: print ("Invalid input!") elif n <= 1: return n else: return fibonacci_1 (n-1)+fibonacci_1 (n-2) n = int (input ("Enter a number: ")) nth_fib = fibonacci_1 (n) print ("The {} th fibonacci number is {}.". format (n, nth_fib)) Implementation 2 def fibonacci_2 (n) : if n<0: return "Invalid Input" if n<=1: return n fib= [0] (n+1) fib[0] = 0 fib[1] = 1 for i in range (2, n+1): fib[i] = fib[i-1] + fib[i-2] return fib[n] n = int (input ("Enter a number: ")) nth_fib = fibonacci_2 (n) print("The {} th fibonacci number is {}.". format (n, nth_fib))

a) You are given two different codes for finding the n-th Fibonacci number. Find the time complexity of both implementations and compare the two. Implementation 1 def fibonacci_1 (n) : if n < 0: print ("Invalid input!") elif n <= 1: return n else: return fibonacci_1 (n-1)+fibonacci_1 (n-2) n = int (input ("Enter a number: ")) nth_fib = fibonacci_1 (n) print ("The {} th fibonacci number is {}.". format (n, nth_fib)) Implementation 2 def fibonacci_2 (n) : if n<0: return "Invalid Input" if n<=1: return n fib= [0] (n+1) fib[0] = 0 fib[1] = 1 for i in range (2, n+1): fib[i] = fib[i-1] + fib[i-2] return fib[n] n = int (input ("Enter a number: ")) nth_fib = fibonacci_2 (n) print("The {} th fibonacci number is {}.". format (n, nth_fib))

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

Similar questions

Given is the code to print numbers from 1 to n in increasing order recursively. But it contains few bugs that you need to rectify such that all the test cases pass.Input Format :Integer nOutput Format :Numbers from 1 to n (separated by space)Constraints :1 <= n <= 10000Sample Input 1 : 6Sample Output 1 :1 2 3 4 5 6Sample Input 2 : 4Sample Output 2 :1 2 3 4.
write in java
Given an integer N and a base X, the task is to find the minimum number of operations required to represent N as a sum of the distinct powers of X. In each operation, you can either increment or decrement N. You are allowed to make the given operation any number of times Examples: Input: N = 7, X = 3 Output: 3.
Using recursion, write a Java program that takes an input ‘n’ (a number) ( user should gives the n value if user asks fibonacci series of 20 then it should display 20 numbers of fibonacci)from a user to calculate and print out the Fibonacci using the following modified definition: F(N) = 1 if n = 1 or n = 2 = F((n+1)/2)2 + F((n-1/2)2 if n is odd = F(n/2 + 1)2 – F(n/2 – 1)2 if n is even
Please convert Mutual Recursion to Java. See attached image. Thank you.
The “odd/even factorial” of a positive integer n is represented as n!! and is defined recursively as: a. (n)*(n-2)*(n-4)………*(2) if n is even. For example, 6!! = 6*4*2 = 48 b. (n)*(n-2)*(n-4)*…….*(5)*(3)*(1) if n is odd. For example, 7!! = 7*5*3*1 = 105. Come up with a recursive definition for n!! and use it to guide you to write a method definition for a method called “oddevenfact” that recursively calculates the odd/even factorial value of its single int parameter. The value returned by “oddevenfact” is a long.
code in java pls Summary: Given integer values for red, green, and blue, subtract the gray from each value. Computers represent color by combining the sub-colors red, green, and blue (rgb). Each sub-color's value can range from 0 to 255. Thus (255, 0, 0) is bright red, (130, 0, 130) is a medium purple, (0, 0, 0) is black, (255, 255, 255) is white, and (40, 40, 40) is a dark gray. (130, 50, 130) is a faded purple, due to the (50, 50, 50) gray part. (In other words, equal amounts of red, green, blue yield gray). Given values for red, green, and blue, remove the gray part. Ex: If the input is: 130 50 130 the output is: 80 0 80 Find the smallest value, and then subtract it from all three values, thus removing the gray.
Solution needed in java
Use the recursion to solve the following problems using Java Programming Language 1. Calculate the sum of an array of n integers. 2. Compute Powers, p(x,n)=xn 3. Revers an array of n integers 4. Calculate the length of string (number of characters) 5. Implement the tail recursion for problems 1 and 2. Please test the program by using 2 different input sets!
The Fibonacci algorithm is a famous mathematical function that allows us to create a sequence of numbers by adding together the two previous values. For example, we have the sequence:1, 1, 2, 3, 5, 8, 13, 21…Write your own recursive code to calculate the nth term in the sequence. You should accept a positive integer as an input, and output the nth term of the sequence.Once you have created your code, add comments describing how the code works, and the complexity of any code you have created.
Consider the below recursive function: public static void func (int n) if (n == 0) return; else { func(n-2); System.out.println(n); } Draw activaiton frames with n=8 and determine the output produced by this method.
Which is the base case of the following recursion function: def mult3(n): if n == 1: return 3 else: return mult3(n-1) + 3 else n == 1 mult3(n) return mult3(n-1) + 3