Question

Please Answer In Details Show all Steps: Implement two C++ programs to generate Fibonacci sequence (one...

Please Answer In Details Show all Steps:

Implement two C++ programs to generate Fibonacci sequence (one using recursion, one using non-recursion structure); analyze their complexity using O notation

Homework Answers

Answer #1

Iterative (non-recursive)

#include<iostream>
#include<stdio.h>
using namespace std;
int fibonacciiterative(int n)
{
    if(n==0)
        return 0;
    if(n==1)
        return 1;
    int a = 0;
    int b = 1;
    int c = 0;
    for (int i = 2; i <= n; ++i)
    {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}
int main(){

cout <<"The seventh fibonacci number is: " << fibonacciiterative(7) << endl;

}
===================================================================================
Recursive Fibonacci

#include <iostream>

using namespace std;

int fibonacciRecursive(int x) {
    if (x == 0)
        return 0;
    else if(x==1)
        return 1;
    else
        return fibonacciRecursive(x-1)+fibonacciRecursive(x-2);

}

int main() {
    cout <<"The seventh fibonacci number is: " << fibonacciRecursive(7) << endl;
}
                                           
===============================================================================
Adding Image and Output:-
                                                                                                                                    



Time Complexity :

For Recursive Implementation: T(n) = T(n-1) + T(N-2) , which tends to exponential time complexity
=> O(2n)

For Iterative Implementation: Time complexity is Linear => O(n)

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Convert 431610 to Hexadecimal. Please show all the steps, Please type answer and steps do not...
Convert 431610 to Hexadecimal. Please show all the steps, Please type answer and steps do not upload a picture
Please show all steps thank you. Determine the smallest n such that there exists nonisomorphic graphs...
Please show all steps thank you. Determine the smallest n such that there exists nonisomorphic graphs of order n with the same degree sequence. Justify your answer.
(SINCE THE VERY BEGINNING, PLEASE SHOW ALL THE STEPS IN YOUR CALCULATION ONE BY ONE. PLEASE...
(SINCE THE VERY BEGINNING, PLEASE SHOW ALL THE STEPS IN YOUR CALCULATION ONE BY ONE. PLEASE DO NOT JUST PUT THE FORMULA WITH THE FINAL ANSWER.) Thank you for your help. We want to compare the variation in diameters of an engine part produced by Manufacturer Alpha against those produced by Manufacturer Beta. Sample variance for Manufacturer Alpha, based on n=10 samples, is s12= 0.0003. In contrast, the variance of the diameter measurements for a sample of 20 from Manufacturer...
Please answer all parts of Question 1. Please show all work and all steps. 1a.) Find...
Please answer all parts of Question 1. Please show all work and all steps. 1a.) Find the equilibrium of x' = x + 1 y' = x + 3y - 1 1b.) Find a, b such that the equilbrium of x' = x + 3y + a y' = x - y + b is (1,2) 1c.) Find alpha, beta such that x' = (alpha)(x) + y y' = -2x + (beta)(y) is hamiltonian.
Show all steps please Using Matlab: Generate a random signal ‘x’ with a length of 8000...
Show all steps please Using Matlab: Generate a random signal ‘x’ with a length of 8000 and sampling rate of 8kHz. Plot a section of the signal In the time domain. Is it possible to observe significant trends in the time domain signal? Plot the magnitude of the DFT of segments of ‘x’ of different lengths. Use a decibel scale for the vertical axis. What do you observe as the segment length increases? Use the Matlab function ‘periodogram’ to obtain...
Please show all the work and answer all the questions! Draw a detailed reaction coordinate and...
Please show all the work and answer all the questions! Draw a detailed reaction coordinate and list all of the steps for an enzyme that catalyzes the conversion of substrates A and B to the products P and Q via a random sequential mechanism. Draw the reaction coordinate for the non-enzyme catalyzed reactions too.
---------------- Overview: ---------------- This lab will consist of several independent exercises that must all use recursion...
---------------- Overview: ---------------- This lab will consist of several independent exercises that must all use recursion to solve various problems. Some problems will have fairly short solutions, but declaring and using classes/objects is still required. Some could benefit from having some kind of data structure being passed between calls. Feel free to use your LinkedList if you think it could help. Some solutions will be a mix of iteration and recursion, but all solution need to be recursive in some...
PLEASE EXPLAIN AND SHOW ALL STEPS USED TO GET TO ANSWER! THX! A jar has 2...
PLEASE EXPLAIN AND SHOW ALL STEPS USED TO GET TO ANSWER! THX! A jar has 2 red marbles and 3 blue marbles. Two marbles are drawn at random without replacement from the jar. Find the probability that the second marble is red. Find the probability that the second marble is red, given that the first is blue.   
Please answer all parts of the following question. Please show all work and all steps. 1a.)...
Please answer all parts of the following question. Please show all work and all steps. 1a.) Let Xn be a Marcov chain with the states S = {0,1} starting from 0. The transition probability is given by p = ( 1/3 2/3) 1/2 1/2 Compute P(X2=1) and compute P(X3=0 given X2=1) 1b.) Suppose that T1 and T2 are stopping times. Determine whether the following are stopping time or not: (1) T1 + T2, (2) T1 − 1 (assuming T1 ≥...
Please show all steps, thank you! a) Verify that the functions below solve the system: x(t)...
Please show all steps, thank you! a) Verify that the functions below solve the system: x(t) = c1e^5t + c2e^-t y(t) = 2c1e^5t - c2e^-t Do not solve the system dx/dt = x + 2y dy/dt = 4x +3y b) Solve the system using Operator D elimination. Write the answer both in scalar and vector form. Please show all steps! dx/dt = x + 2y dy/dt = 4x + 3y