Scribd
Upload
35 views2 pages

DAA Assignment 01

The document contains instructions for a computer science assignment on algorithm design and analysis. It includes 3 questions - the first asks to rank functions by asymptotic growth rate, the second asks to use Big-Oh notation to prove time complexities, and the third asks to find the time complexity of a nested for and while loop algorithm.

Uploaded by

Nagina Gul
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
35 views2 pages

DAA Assignment 01

The document contains instructions for a computer science assignment on algorithm design and analysis. It includes 3 questions - the first asks to rank functions by asymptotic growth rate, the second asks to use Big-Oh notation to prove time complexities, and the third asks to find the time complexity of a nested for and while loop algorithm.

Uploaded by

Nagina Gul
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

NATIONAL INSTITUTE OF MODERN LANGUAGES RWP

COMPUTER SCIENCE DEPARTMENT

Total Marks:

Obtained Marks:

Design and Analysis of


Algorithm
Assignment # 01
Last date of Submission: Monday 3rd, Oct, 2022

Submitted To: Ms. Aunsia Khan


______________________________________________________________________________

Student Name:
______________________________________________________________________________

Reg Number:
_______________________________________________________________________________

Design and Analysis of Algorithm BSCS- 35 NUML-RWP


NATIONAL INSTITUTE OF MODERN LANGUAGES RWP

COMPUTER SCIENCE DEPARTMENT

Instructions:
 Copied or shown assignments will be marked zero.
 Late submissions are not entertained in any case.
 Hand written assignments are not accepted.
 If you have any questions, you can e-mail it on mailto: [email protected]

Question 01: Group and rank the following functions by asymptotic growth rate in non-
decreasing order:

264−1 , n3 , 0 .0001 n2 , 1000 n , Logn2,2log n,nlogn ,n 2n,21000,n ,n2 logn,¿ Logn ,n100 , 4 n , logn 3 , nn ,
3
n log n

Question 02: Use the definition of Big-Oh to prove that


1. 0.001n3 − 1000n2 log n − 100n + 5 = O (n3).
2. n/100 = O(n)
3. n2 +100nlogn + 10n + 1000 = O(n2)

Question 03: Find out the time complexity of given algorithm. Write complete steps to find
the solution.

For (int i = 1 ; i <= n; i++)


{
For (int j = 1; j <= i2; j++)
{
int k = 0;
while (k > 10)
{
set of statements;
k--;
}
}
}

Design and Analysis of Algorithm BSCS- 35 NUML-RWP

You might also like