1-) Answer in detail the questions that are shown below by using asymptotic notations, yes / no answers and plagiarisation from the web will not be accepted.
Explain why the statement, “The running time of algorithm A is at least O(n2),” is meaningless.
Are the following true?
2n+1 = O(2n)?
22n = O(2n)?
Are the functions below polynomially bounded?
[log n]!
[log log n]!
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)
n2 / log n
(log n)log n
√n
(log n)log n
∑ni=1 ik
n(log n)2
n/ log n
(log n) 3
2(log2 n) ^2
nk+1
f)
100n + log n
n + (log n)2
g)
n 1/2
5 log2 n
h)
n 0.1
(log n) 10
3-) For each of the following functions, indicate the function’s growth rate when its input is increased by one (n - n+1) and order the functions according to their growth rates.
Log2 n, √n, n!, n2, n, 2n, 3n
4-) Analyze the complexity in time (big -Oh notation) of the following operations at a given binary search tree (BST) that has height n:
FindMax.
Insert a new element.
Delete a leaf node.
Printing BST using the in order traversal
5-) Find the complexity in time (big -Oh notation) of the following program.
a)
void function(int n)
{
int count = 0;
for (int i=n/2; i<=n; i++)
for (int j=1; j<=n; j = 2 * j)
for (int k=1; k<=j; k = k * 2)
count++;
}
Note:
Your submissions will be handwritten
You can deliver your homework to TA M. Burak Koca until 17:00 on due date (room 119).
Do your homework personally, group studies will be considered as cheating.
