1 Faculty of Engineering and Architecture Computer Engineering Department COM 400 – Analysis of Al

1 Faculty of Engineering and Architecture Computer Engineering Department COM 400 – Analysis of Algorithms HOMEWORK #1 Academic Year: Spring 2014-15 Due Date: 13.03.2015 (At class hour) Instructor: Assoc. Prof. Dr. Hürevren KILIÇ Question 1: (10 + 10 = 20 points) i. Prove that 2n3 + n + 4 = O(n3) By definition, we can write that f(n) = 2n3 + n + 4 and g(n) = n3. So, we need to find c and n0 values that satisfies below inequality: cn3 = 2n3 + n + 4 c = 2 + 1/n2 + 4/n3 if we take c=2 and n0=1 then the above inequality is satisfied for all n = n0. Existence of such positive constants c and n0 completes the proof. ii. Prove that n3 + 1 = ?(n) Solution 1: By definition, we can write that f(n) = n3 + 1 and g(n) = n. Since, and exists. We can conclude that g(n) = n constitutes an asymptotically NOT tight bound on f(n) = n3 + 1. Solution 2: By definition, ?(g(n)) = {f(n) : for any positive constant c > 0, there exists a constant n0 > 0 such that 0 = cg(n) < f(n) for all n = n0}. Then, f(n) = n3 + 1 and g(n) = n. So, for any arbitrary value of c, we must be able to find corresponding n0 that satisfies below inequalities: 0 = cn < n3 + 1 0 = c < n2 + 1/n If we take for example n0 = c, whatever the value of c > 0 is, the above inequality holds for all n = n0. 2 Question 2: (40 points) Analyze the following algorithm written in pseudo-code for its worst-case and best-case running time complexity. Note that the logic of the algorithm is not important. Assume that length(A) is computab

Document Preview:

Faculty of Engineering and Architecture
Computer Engineering Department
COM 400 – Analysis of Algorithms
HOMEWORK #1
Academic Year: Spring 2014-15
Due Date: 13.03.2015 (At class hour)
Instructor: Assoc. Prof. Dr. Hürevren KILIÇ
Question 1: (10 + 10 = 20 points)
3 3
i. Prove that 2n + n + 4 = O(n )
3 3
By definition, we can write that f(n) = 2n + n + 4 and g(n) = n . So, we need to find c
and n values that satisfies below inequality:
0
3 3
cn = 2n + n + 4
2 3
c = 2 + 1/n + 4/n
if we take c=2 and n =1 then the above inequality is satisfied for all n = n . Existence of
0 0
such positive constants c and n completes the proof.
0
3
ii. Prove that n + 1 = ?(n)
3
Solution 1: By definition, we can write that f(n) = n + 1 and g(n) = n. Since,
and exists. We can conclude that g(n) = n constitutes an
3
asymptotically NOT tight bound on f(n) = n + 1.
Solution 2: By definition, ?(g(n)) = {f(n) : for any positive constant c > 0, there exists a
3
constant n > 0 such that 0 = cg(n) < f(n) for all n = n }. Then, f(n) = n + 1 and g(n) = n.
0 0
So, for any arbitrary value of c, we must be able to find corresponding n that satisfies
0
below inequalities:
3
0 = cn < n + 1
2
0 = c < n + 1/n
If we take for example n = c, whatever the value of c > 0 is, the above inequality holds
0
for all n = n .
0
1Question 2: (40 points)
Analyze the following algorithm written in pseudo-code for its worst-case and best-case
running time complexity. Note that the logic of the algorithm is not important. Assume that
length(A) is computable in T(n) where n is the size of the array A. Be careful about indentations
made in the code.
COST TIMES
EXAMPLE(A)
BEST WORST
c 1 1
1
1 n = 2;
c 1 1
2
2 m = n + 1;
c ...