Description
1-) Answer in detail the questions that are shown below by using asymptotic notations, yes / no answers and plagiarizing from the web will not be accepted.
-
Is the following statement scientifically sound? :“The running time of algorithm A is at least O(n2)”?
-
Are the following true?
-
2n+1 = O(2n)?
-
22n = O(2n)?
-
-
Let f (n) and g(n) be asymptotically nonnegative functions. Is the equation: max(f (n), g(n)) = Θ(f(n) + g(n)) true?
2-) In each of the following situations, indicate whether f ϵ O(g), or f ϵ Ω(g), or both (in which case f ϵ Θ(g)).
-
f(n)
g(n)
a)
n1.01
nlog2n
b)
n!
2n
c)
√n
(log n)3
d)
n2n
3n
e)
∑ni=1 ik
nk+1
f)
2n
2n+1
g)
n 1/2
5 log2 n
h)
log2n
log3n
3-) List the following functions according to their order of growth and prove your assertions.
Logn, √ + 10, n + 10, 10n, 100n, n2logn, 32logn, n6
4-) Analyze the complexity in time (big -Oh notation) of the following operations at a given binary search tree (BST) that has height n:
-
FindMin.
-
Searching a node.
-
Delete a leaf node.
-
Merging with another BST that has height n.
5-) Find the time complexity (big -Oh notation) of the following program.
void function(int n)
{
int count = 0;
for (int i = 2; i <= n; i++)
if (i % 2 == 0)
{
count++;
}
else
{
i = (i – 1) * i;
}
}
Notes:
-
Your submissions will be handwritten.
-
You can deliver your homework to TA M. Burak Koca until 16:45 on due date (room 119).
-
Do your homework personally, group studies will be considered as cheating.