Scribd
Upload
19 views2 pages

Lab 4

The document contains a practice worksheet with various questions related to algorithm analysis, including worst-case and average-case running times, time complexity of code fragments, asymptotic relationships, and recurrence relations. It includes multiple-choice questions, ordering functions by growth, and true/false statements about algorithmic properties. Additionally, it presents specific recurrence relations to analyze for their complexities.

Uploaded by

vk640
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
19 views2 pages

Lab 4

The document contains a practice worksheet with various questions related to algorithm analysis, including worst-case and average-case running times, time complexity of code fragments, asymptotic relationships, and recurrence relations. It includes multiple-choice questions, ordering functions by growth, and true/false statements about algorithmic properties. Additionally, it presents specific recurrence relations to analyze for their complexities.

Uploaded by

vk640
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/ 2

Practice Worksheet

Ques.1 Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm
executed on an input of size n. which of the following is ALWAYS TRUE?

(a) A(n) = Ω (W(n)) (b) A(n) = Ɵ (W(n)) (c) A(n) = O (W(n)) (d) None of the above

Ques.2 Arrange these functions by order of growth from highest to lowest


100*n2 , 1000, 2n , 10*n, n3 , 2*n

Ques.3 What is the time complexity of the following code fragments?


(a) int fun(int n) for( k = 1; k <= n; k = k * 2)
{ count++;
int count = 0; }
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for(k = 0; k < n; k++) (f) void fun(int n, int k)
count += 1; {
return count; for (int i=1; i<=n; i++)
} {
int p = pow(i, k);
(b) int a = 0; for (int j=1; j<=p; j++)
for (i = 0; i < N; i++) { {
for (j = N; j > i; j--) { // Some O(1) work
a = a + i + j; }
} }
} }

(c) int i, j, k = 0; (g) fun(int n)


for (i = n / 2; i <= n; i++) {
{ for(i = 1; i <= n; i = i*2)
for (j = 2; j <= n; j = j * 2) {
{ for(j = 1; j <= i; j = j*2)
k = k + n / 2; printf(“ Hii ”);
} }
} }

(d) int fun(int n) (h) void fun(int n, int arr[])


{ {
for (int i = 1; i <= n; i++) int i = 0, j = 0;
{ for(; i < n; ++i)
for (int j = 1; j < n; j += i) while(j < n && arr[i] < arr[j])
{ j++;
// Some O(1) task }
}
} } (i) void function(int n)
{
int count = 0;
(e) void fun() for (int i=n/2; i<=n; i++)
{ for (int j=1; j+n/2<=n; j = j++)
int i, j, count = 0; for (int k=1; k<=n; k = k * 2)
for ( i = n/2; i <= n; i++) count++;
for ( j = 1; j <= n; j = j * 2) }
Ques4. For the functions, nk and cn, what is the asymptotic relationship between these functions?
Assume that k >= 1 and c > 1 are constants.

Ques5. Decide whether these statements are True or False:


1. If f(n) = Θ(g(n)) and g(n) = Θ(h(n)), then h(n) = Θ(f(n))
2. If f(n) = O(g(n)) and g(n) = O(h(n)), then h(n) = Ω(f(n))
3. If f(n) = O(g(n)) and g(n) = O(f(n)) then f(n) = g(n)
𝑛
4. = Ω(n)
100

Ques6. Find the complexity of below recurrence:


1, 𝑛=0
𝑇(𝑛) = {
3𝑇(𝑛 − 1), 𝑛>0

Ques7. Find the complexity of below recurrence:


1, 𝑛=0
𝑇(𝑛) = {
2𝑇(𝑛 − 1) − 1, 𝑛>0

Ques8. Find the complexity of below recurrence:


1, 𝑛=0
𝑇(𝑛) = { 2
7𝑇(𝑛/2) + 3𝑛 + 2, 𝑛>0

You might also like