Scribd
Upload
2 views1 page

Asymptotic Notations and Complexity Analysis

The document discusses complexity analysis of functions and explicit notations related to asymptotic analysis. It provides examples of functions and asks to compute their time complexity and determine relationships between asymptotic notations. The first section provides three functions and asks to compute their time complexity in terms of Θ(.) bound. The second section recalls definitions of different asymptotic notations and provides examples of functions to determine values of c and n0 to prove relationships.

Uploaded by

Sara
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 views1 page

Asymptotic Notations and Complexity Analysis

The document discusses complexity analysis of functions and explicit notations related to asymptotic analysis. It provides examples of functions and asks to compute their time complexity and determine relationships between asymptotic notations. The first section provides three functions and asks to compute their time complexity in terms of Θ(.) bound. The second section recalls definitions of different asymptotic notations and provides examples of functions to determine values of c and n0 to prove relationships.

Uploaded by

Sara
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

[CSN212] Study Group 1

Asymptotic Notations

1 Complexity of Functions
Compute the time complexity of the following functions, in terms of Θ(·) bound
1. void function(int n){
int i = 1, s = 1;
while (s < n) {
s = s + i; i++;
}
}
2. void fun(int n)
{
int i = 1;
while (i < n) {
int j = n;
while (j > 0) {j = j / 2;}
i = i * 2;
}
}
3. void fun(int n)
{
solution = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j = j + i)
solution = solution +1;
}

2 Explicit Notations
Recall the definition of O(·), Ω(·), o(·), ω(·), θ(·) from the class.
Find the value of c and n0 (wherever required) for proving all possible relationships wherever applicable.

1. f (n) = 13n3 + 12n + 11 4. f (n) = 2n − 500n3 + 10


g(n) = 2000n2 + 100000. g(n) = 3n + 10n2 + 200.
2. f (n) = n2 − 1000n + 3
g(n) = 1200n + 15.
5
3. f (n) = 19000n2 + 5n + 3 5. f (n) = n log n + n2
log log n
g(n) = n2 − 109 . g(n) = n log n + 100n.

You might also like