Scribd
Upload
2 views

Tutorial 1 algorithms

The document outlines a tutorial for the MCA course on Algorithm Design and Complexity Analysis (ADCA) with objectives focused on comparing functions and counting loop executions. It includes various problems related to algorithm efficiency, time complexity, and growth order of functions. The tutorial is designed for first-semester students and covers a range of algorithmic scenarios and their computational implications.

Uploaded by

namojusumanth
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
2 views

Tutorial 1 algorithms

The document outlines a tutorial for the MCA course on Algorithm Design and Complexity Analysis (ADCA) with objectives focused on comparing functions and counting loop executions. It includes various problems related to algorithm efficiency, time complexity, and growth order of functions. The tutorial is designed for first-semester students and covers a range of algorithmic scenarios and their computational implications.

Uploaded by

namojusumanth
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

School of Computer Science Engineering and Technology

Course- MCA Type- Core Course


Code- CMCA502 Course Name-ADCA
Year- 2022 Semester- Odd
Date- 22-09-2022 Batch- 1rst Sem

Tutorial: 01
Objective 1: Comparing two functions
Objective 2: Counting the loop execution
Tut No. Name CO 1 CO 2 CO 3
1. Tutorial:01 √

1. Two alternative packages A and B are available for processing a database


having 10k records. Package A requires 0.0001n2 time units and
package B requires 10nlog10n time units to process n records. What is the
smallest value of k for which package B will be preferred over A?

2. Suppose an algorithm ALG requires n4 operations and the machine


executes 106operations per seconds. What is the running time of ALG on
that machine if n =1000?

3. Algorithms A and B spend exactly TA(n) = cAn log2n and TB(n) = cBn2
microseconds, respectively, for a problem of size n. Find the best
algorithm for processing n = 220 data items if the algorithm A spends 10
microseconds to process 1024 items and the algorithm B spends only 1
microsecond to process 1024 items.

4. Arrange the following function in increasing order of their growth


a. 10, √n, n, log2n, 100/n
b. 2n, n!, nlogn
c. 2n, n3/2, nlog2n, nlog2n
d. n, log2n, 2n, nn, n!
5. Find the time complexity of following programs
a. for(i =1; i<=n; i++)
k = k + 1;
b. for(i =1; i <= n; i++)
for(j =1; j <= n; j++)
k = k + 1;

c. for(i =1; i<=n; i++)


k = k + 1;
for(i =1; i<= n; i++)
for(j =1; j <= n; j++)
a = a + 5;

d. for(i =1; i<=n2; i++)


k = k + 1;

e. for(i =1; i<= n2; i++)


for(j =1; j <= n; j++)
k = k + 1;

f. for(i =1; i*i<=n; i++)


k = k + 1;

g. for(i =1; i<=n; i= i +2)


k = k + 1;

h. for(i =1; i<=n; i*2)


k = k + 1;

i. for(i =1; i <= n; i++)


for(j =1; j <= n; j = j*2)
k = k + 1;

j. for(i =1; i <= n; i=i*2)


for(j =1; j <= n; j=j*2)
k = k + 1;

k. for(i =1; i <= n; i= i+2)


for(j =1; j <= n; j = j*2)
k = k + 1;

l. for(i = n-5; i <= n+5; i++)


k = k + 1;
m. for(i = n-500; i <= n+500; i++)
for(j =1; j <= n; j = j*2)
k = k + 1;

n. for(i =1; i <= n; i++)


for(j =1; j <= n; j++)
for(k=1; k<=n; k++)
k = k + 1;

o. for(i =1; i <= n; i++)


for(j =1; j <= n; j = j*2)
for(k=1; k<=n; k = k +2)
k = k + 1;

p. for(i =1; i <= 100; i++)


for(j =1; j*j<= n; j++)
for(k=1; k<=n; k= k*2)
k = k + 1;

q. for(i =1; i<=logn; i=i*2)


k = k + 1;

r. for(i =1; i <= 100; i++)


for(j =1; j*j<= logn; j++)
for(k=1; k<=n; k= k*2)
k = k + 1;
s. for(i =1; i <= n; i=i+2)
for(j =1; j*j<= n; j =j*2)
for(k=1; k<=n; k= k*2)
k = k + 1;

You might also like