Scribd
Upload
5 views2 pages

Asymptotic Relationships in Algorithms

This document contains an introduction to algorithms homework assignment from Yerevan State University. It presents two problems on asymptotic analysis: Problem 1-1 asks to sort several groups of functions in increasing order of asymptotic complexity. Problem 1-2 asks to identify the asymptotic relationships between various pairs of functions, choosing from big-O, Ω, and Θ notation. The functions include exponents, logarithms, polynomials, and factorials.

Uploaded by

Hrant Baloyan
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
5 views2 pages

Asymptotic Relationships in Algorithms

This document contains an introduction to algorithms homework assignment from Yerevan State University. It presents two problems on asymptotic analysis: Problem 1-1 asks to sort several groups of functions in increasing order of asymptotic complexity. Problem 1-2 asks to identify the asymptotic relationships between various pairs of functions, choosing from big-O, Ω, and Θ notation. The functions include exponents, logarithms, polynomials, and factorials.

Uploaded by

Hrant Baloyan
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

Yerevan State University

Introduction to Algorithms
Homework 1

Problem 1-1. Asymptotic practice


For each group of functions, sort the functions in increasing order of asymptotic (big-O) complex-
ity:

(a)
f1 (n) = n!
f2 (n) = n(n+1)
2
f3 (n) = 2n
f4 (n) = n+1

(b)
9000000
f1 (n) = 22
f2 (n) = 2100n
f3 (n) = n(n−1)
√2
f4 (n) = n n

(c) √
f1 (n) = nn
f2 (n) = (n + 5)100000
f3 (n) = 2n · ln n
f4 (n) = 12 + 22 + · · · + n2

Problem 1-2. Asymptotic notation

(a) For the functions, nk and cn what is the asymptotic relationship between these func-
tions? Assume that k ≥ 1 and c > 1 are constants. Choose all right answers:

nk is O(cn )
nk is Ω(cn )
nk is Θ(cn )

(b) For the functions, log2 n and log8 n what is the asymptotic relationship between these
functions? Choose all right answers:

a) log2 n is O(log8 n)
b) log2 n is Ω(log8 n)
c) log2 n is Θ(log8 n)

1
(c) What is the asymptotic relationship between the functions n3 log2 n and 3n log8 n?
Choose all right answers:

a)n3 log2 n is O(3n log8 n)


b)n3 log2 n is Ω(3n log8 n)
c)n3 log2 n is Θ(3n log8 n)
(d) For the functions, 8n and 4n , what is the asymptotic relationship between these func-
tions? Choose all right answers:

a)8n is O(4n )
b)8n is Ω(4n )
c)8n is Θ(4n )

(e) For the functions, log2 nlog2 17 and log2 17log2 n , what is the asymptotic relationship
between these functions? Choose all right answers:

a) log2 nlog2 17 is O(log2 17log2 n )


b) log2 nlog2 17 is Ω(log2 17log2 n )
c) log2 nlog2 17 is Θ(log2 17log2 n )

You might also like