[go: up one dir, main page]
Scribd
Upload
28 views3 pages

PracticeQs Recursion

The document contains practice questions on recursion for MCSC 101, authored by Neelima Gupta. It includes problems related to calculating powers, generating Fibonacci sequences, and analyzing time complexities of recursive algorithms. Students are tasked with writing algorithms, deriving their complexities, and comparing recursive and iterative implementations.

Uploaded by

rdxsingh01
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
28 views3 pages

PracticeQs Recursion

The document contains practice questions on recursion for MCSC 101, authored by Neelima Gupta. It includes problems related to calculating powers, generating Fibonacci sequences, and analyzing time complexities of recursive algorithms. Students are tasked with writing algorithms, deriving their complexities, and comparing recursive and iterative implementations.

Uploaded by

rdxsingh01
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Practice Questions on Recursion

MCSC 101

Neelima Gupta

ngupta@cs.du.ac.in

March 1, 2023
Problem 1: x n (Marks: 1 + 2 + 2 + 5)

Consider the following algorithm to compute x n where x is a fixed


small number.
P=x
i=2
while i ≤ n do
P=P*x
i++
end
return P

1. What is the running time complexity of the above algorithm?


2. Write a recursive algorithm of the same complexity. Write and
Solve the recurrence for the time Complexity
3. Write a recursive algorithm of log n running time complexity.
Problem 2: Fibonacci Sequence 2 + 5 + (2 + 2 + 2) +
(2 + 2 +1) = 17
Consider the problem of generating the first n terms of the
Fibonacci sequence and store it in an array F .
1. Write a recursive algorithm for the problem. Call it Algorithm
A. (Marks 2)
2. Derive the time-complexity of your algorithm. Is it
logarithmic, linear or exponential? You can take help of
Internet/Book for this question. No help from friends, Learn
to dig out yourself.(Marks 5)
3. Can you give a linear time implementation of the above
recursive algorithm? (Note that the implementation is still
recursive and not iterative). Justify the complexity of your
algorithm. Call it Algorithm B. What makes Algo B perform
better in terms of time than Algo A. What is this technique
called? (Marks 2 +2 +2)
4. Can you give a linear time iterative algorithm of the same
complexity as that of algorithm B. Justify the complexity of
your algorithm. What is this technique called? (Marks 2 +2)

You might also like