Description
Part 1:
Analyze the time complexity (in most appropriate asymptotic notation) of the following
procedures by your solutions for the Homework 1:
I. Searching a product.
II. Add/remove product.
III. Querying the products that need to be supplied.
Attach the code of your solution for each part just before its analysis.
Part 2:
a) Explain why it is meaningless to say: “The running time of algorithm A is at least O(n2
)”.
b) Let f(n) and g(n) be non-decreasing and non-negative functions. Prove or disprove
that: max(f (n), g(n)) = Θ(f(n) + g(n)).
c) Are the following true? Prove your answer.
I. 2
n+1 = Θ(2n
)
II. 2
2n = Θ(2n
)
III. Let f(n)=O(n
2
) and g(n)= Θ(n
2
). Prove or disprove that: f(n) * g(n) = Θ(n
4
).
Part 3:
List the following functions according to their order of growth by explaining your assertions.
n
1.01, nlog2n, 2n
, √n, (log n)3
, n2n
, 3n
, 2
n+1
, 5 log2
n
, logn
Part 4:
Give the pseudo-code for each of the following operations for an array list that has n elements
and analyze the time complexity:
– Find the minimum-valued item.
– Find the median item. Consider each element one by one and check whether it is the
median.
– Find two elements whose sum is equal to a given value
– Assume there are two ordered array list of n elements. Merge these two lists to get a
single list in increasing order.
Part 5:
Analyze the time complexity and space complexity of the following code segments:
a)
int p_1 (int array[]):
{
return array[0] * array[2])
}
b)
int p_2 (int array[], int n):
{
Int sum = 0
for (int i = 0; i < n; i=i+5)
sum += array[i] * array[i])
return sum
}
c)
void p_3 (int array[], int n):
{
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j=j*2)
printf(“%d”, array[i] * array[j])
}
d)
void p_4 (int array[], int n):
{
If (p_2(array, n)) > 1000)
p_3(array, n)
else
printf(“%d”, p_1(array) * p_2(array, n))
}
RESTRICTIONS:
– Answer in detail the questions by using asymptotic notations.
– Yes / no answers and plagiarisation from the web will not be accepted.
GENERAL RULES:
– For any question firstly use course news forum in Moodle, and then the contact TA.
– You can submit assignment one day late and will be evaluated over sixty percent (%60).
REPORT RULES:
– All the analysis must be stated in the report/answer sheet in details.
– The report may be handwritten (only for this homework) if you want but, it must be scanned
well and submitted to Moodle.
GRADING :
– Part 1: 20 pts
– Part 2: 10 pts
– Part 3: 25 pts
– Part 4: 30 pts
– Part 5: 15 pts
– Disobey restrictions: -100
– Cheating: -200
– Your assignment is evaluated over 100 as your performance.
CONTACT :
– Teaching Assistant : Mehmet Burak Koca
– b.koca@gtu.edu.tr