Objectives: Understanding Big O notation and runtime analysis.
Problem 1: [20 Points]
Order the following list of functions by the Big O notation, group together those functions that are Big Theta of one another.
| 6nlgn |
2^(1000) |
lglgn |
(lgn)^2 |
2^(lgn) |
|---|---|---|---|---|
2^2^n |
Sqrt(n) |
n^0.01 |
1/n |
4n^(3/2) |
5n |
3n^(0.5) |
n^3 |
4^(lgn) |
4^n |
2n(lgn)^2 |
nlog4n |
Sqrt(lgn) |
(n^2)(lgn) |
2^n |
Problem 2:[5 Points]
Algorithm A uses 10nlgn operations, while algorithm B uses n2 operations. Determine the value
of n0, such that A is better than B for all n>=n0.
Problem 3:[5 Points]
Show that nlgn is O(n3/2)
(use the definition: give a c and an n0)
Problem 4: [15 Points]
For each part below, give the running time in Big O notation in terms of n.
Part A:
void funA(int n)
{
int a;
for(int i=0; i < n; i++)
{
a= i;
}
}
Part B:
void funB(int n)
{
int a;
for(int i=0; i < n; i+=2)
{
a = i;
}
}
Part C:
void funC(int n)
{
int a;
for(int i=0; i < n*n; i++)
{
a = i;
}
}
Part D:
void funD(int n)
{
int a;
for(int i=0; i < n; i++)
{
for(int j=0; j <=i; j++)
{
a=i;
}
}
}
Part E:
void funE(int n)
{
int a;
for(int i=0; i < n*n; i++)
{
for(int j=0; j <=i; j++)
{
a=i;
}
}
}
Problem 5 [5 Points]:
Sometimes multiplying sizes of nested loops is an overestimate for the Big O running time when inner loops are executed infrequently. Keeping that in mind give the running time in Big O for the following code fragment
void fun(int n)
{
int a;
for(int i=0; i < n; i++)
{
for(int j=0; j <=i*i; j++)
{
if(j % i == 0)
{
for(int k = 0; k < j; k++)
{
a=i;
}
}
}
}
}