Scribd
Upload
22 views

DAA Unit 1 Analysis

The document discusses analyzing algorithms and determining their time and space complexity using asymptotic analysis. It contains 11 questions about asymptotic notations, solving recurrence relations, analyzing recursive and iterative algorithms, and determining the time and space complexity of various code snippets. Key areas covered include defining asymptotic notations like Big-O notation, using substitution methods to solve recurrence relations, analyzing sorting and searching algorithms, and steps for mathematically analyzing recursive algorithms.

Uploaded by

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

DAA Unit 1 Analysis

The document discusses analyzing algorithms and determining their time and space complexity using asymptotic analysis. It contains 11 questions about asymptotic notations, solving recurrence relations, analyzing recursive and iterative algorithms, and determining the time and space complexity of various code snippets. Key areas covered include defining asymptotic notations like Big-O notation, using substitution methods to solve recurrence relations, analyzing sorting and searching algorithms, and steps for mathematically analyzing recursive algorithms.

Uploaded by

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

DAA Unit 1 Analysis

- - - 1. Explain asymptotic notations in detail with example and graph.


Define asymptotic notations.Explain them in brief. <10M>

- - 2. Compute the time complexity of the following recursive function :


void Test (int n)
{
if (n>0)
{
for(i=0;i<n;i++)
{
Printf(“%d”,n); T = O (n2)
}
Test(n-1);
}
} <10M>

3. (a) Prove that n2 + 2n + 3 is O(n2)


(b) Disprove that 2n3 is not O(4n2) <10M>

4. Consider a recurrence relation T(n)= T(n-1)+n for n>0 with initial condition T(n) =1,n=0.
Solve it using Substitution method. T = O (n2) <4M>

5. Analyze the following code snippet and write the time and space complexity.
(a) for(i=n;i>=1;i=i/2)
{
for(j=1;j<=m;j*=2)
{
stmt; T = O (log2n * log2m) S = O (1)
}
}
(b) while(n>0)
{
Ans+=n;
n=n/2; T = O (log2n) S = O (1)
stmt;
}
(c) void T1(int n)
{
If(n>0)
{
stmt; T = O (n) S = O (n)
T1(n-1);
} <6M>
}

6. Write an algorithm for quick sort and discuss its time and space complexity. <6M>
7. Write iterative and recursive algorithm for finding an element in sequential order.
Compare and contrast both iterative and recursive approach in terms of time and
space complexity. <10M>

8. Compare the order of growth n(n-1)/2 and n2. <2M>

9. What are the basic asymptotic efficiency classes? <2M>

10. List out the steps in Mathematical Analysis of recursive Algorithms with an example. <8M>

11. Construct a recursion tree for the recurrence T(n)=3T(n/4)+cn2 and calculate it’s
time complexity. <8M>

You might also like