Homework 1 Com S 311 Due: Sep 3, 11:59PM Total Points: 100
Late submission policy. If you submit by Sept 4, 11:59PM, there will be 20% penalty. That is, if your score is x points, then your final score for this homework after the penalty will be 0.8 × x. Submission after Sept 4, 11:59PM will not be graded without explicit permission from the instructors.
Submission format. Your submission should be in pdf format. Name your submission file:
If you are planning to write your solution and scan+upload, please make sure the submission is readable (sometimes scanned versions are very difficult to read – poor scan quality to blame).
If you plan to snap pictures of your work and upload, please make sure the generated pdf is readable – in most cases, such submissions are difficult to read and more importantly, you may end up submitting parts of your work.
If you would like to type your work, then one of the options you can explore is latex.
Organization of the assignment. This homework has two parts. Part 1 of the assignment will be graded explicitly and strictly. That is, for every solution you provide, if it is not correct or partially correct, you will be provided with basic comments outlining the problem with your solution. If you correctly answer all questions in Part 1 and submit within the specified deadline (not late), you will secure 100% points. As noted in the syllabus, any re-grade request must be submitted within one week of the release of the grades.
Part 2 of the assignment will not be graded explicitly. If you write some reasonable answers (as assessed by the teaching staff members) for all the questions (Part 2 has two questions), you can get at most 20 points (10 points/question; there are no partial credits for the answering only parts of any question). This can be counted as extra credits for this assignment. We will not consider requests to re-grade Part 2 of the assignment.
Learning outcomes.
1. Determine whether or not a function is Big-O of another function 2. Analyze asymptotic worst-case time complexity of algorithms
1
1
1.
Part 1
Prove or disprove the following statements. Provide a proof for your answers.
If you are showing that if f(n) ∈ O(g(n)), then you must show that there are some c > 1 and N > 0 such that ∀n ≥ N, f(n) ≤ cg(n). You will have to show the range of values of c and N for which the claim is true.
On the other hand, if you are showing that if f(n) ̸∈ O(g(n)), then you must prove why there exists no c > 1 or N > 0 such that ∀n ≥ N, f(n) ≤ cg(n).
(a) 2n3 +35n+46∈O(n3)
Proof. The following inequalities hold for every n ≥ 1
2n3 +35n+46≤2n3 +35n3 +46n3
= 83n3
We take c = 83 and N = 1, Thus we have
∀n≥1(2n3 +35n+46)≤83n3
So 2n3 + 35n + 46 ∈ O(n3). (b) 6n2 −41n+2∈O(n2).
Ans. The following inequalities hold for every n ≥ 1 6n2 −41n+2≤6n2 +42n2 +2n2
We take c = 50 and N = 1.
= 50n2
∀n≥1,(6n2 −41n+2)≤50n2
Thus 6n2 − 41n + 2 ∈ O(n2) (c) ∀a≥1:2n ∈O(2n−a)
Ans. Note that 2n ≤ 2n . 2a
Wetakec=2a andN=1,thus
∀n ≥ 1, 2n ≤ 2a × 2n−a
thus 2n ∈ O(2n−a) for every a ≥ 1. (d) ∀a ≥ 1 : O(log2n) ∈ O(logan))
(30 Points)
Ans. Notethatlog2n=logan×log2aforeverya. Thusforagivena,wetakec=log2a and N = 1, Now
∀n ≥ 1, log2n ≤ log2 a × logan Thus log2n) ∈ O(logan)) for every a ≥ 1.
2
(e) ∀a≥1:aan+1 ∈O(aan).
Ans. Suppose that there exist c and N such that
∀n≥N,aan+1 ≤c×aan Divide both sides of the inequality by aan , to obtain
∀n≥N,aan ≤c
This is a contradictions as aan is a growing function and c is a constant. Thus aan+1 ∈/
O(aan )
(f) If f(n) ∈ O(g(n)) and h(n) is any positive-valued function, then f(n)×h(n) ∈ O(g(n)× h(n)).
Ans. Since f(n) ∈ O(g(n), there exist c and N such that ∀n ≥ Nf(n) ≤ c × g(n)
Since h(n) is a positive valued function we can multiply both sides of the inequality by h(n)
∀n ≥ Nf(n)× ≤ c × g(n) × h(n) Thus f(n) × h(n) ∈ O(g(n) × h(n)).
2. Formally derive the run time of the each algorithm below as a function of n and determine its Big-O upper bound. You must show the derivation of the end result. Simply stating the final answer without any derivation steps will result in 0 points. (30 Points)
(a) for (i = 1; i < n-8; i++) {
for (j = i; j < i+8; j = j++) {
}}
Ans. Each iteration of the inner loop take c1 time which is a constant. Time taken by the inner loop is
i+7
c1 = 8c1
j=i
During every iteration of outerloop, the inner loop is run once and a constant c2 number
of operations are performed. Thus one iteration of outer loop takes time c2 + 8c1
This the total time is
n−7
[c2 + 8c1]
i=1
3
(b) for i in the range [1, n] { for j in the range [i, n] {
}}}
n n j−i c
i=1 j=i k=1
n n
n−7
[c2+8c1] =
n−7 n−7
c2 +8c1 i=1 i=1 i=1
= = ∈
(n−7)c2 +8(n−7)c1 (8c1+c2)n−7c2−56c1 O(n)
for k in the range [1, j-i] {
Each iteration of inner most loop has constant many operations. Inner loop is performed while k ranges over [1, j − i].
Each iteration of the middle loop performs innermost loop. Middle loop is performed while j ranges over [i,n]. Each iteration of the outer loop performs the middle loop. Outer loop is done while i ranges over [1, n]. Thus runtime is bounded by
n n j−i c
i=1 j=i k=1
= c(j−i) i=1 j=i
nnn
= [cj−ci] i=1 j=i j=i
n n(n + 1) i(i − 1)
= c[ 2 − 2 −ci(n−i+1)]
i=1
nn2ni2i 2
= c[2 +2− 2 +2−ni+i −i] i=1
c[2 +2+2−ni−2]
n3 n2 n(n+1)(2n+1) n2(n+1) n(n+1)
∈ O(n3)
nn2ni2 i
=
=c[2+2+ 12 −2−4]
i=1
(c) x = pow(2, n); i = 1;
while i <= x {
for j in range [1, i] {
4
}
Note that
i=i*2 }
Assume that pow(2, n) is computed magically in constant time.
Let c1 be the constant associated with the inner loop and c2 be the constant associated with the outer loop, and let c = max{c1, c2}. Time for inner loop is atmost
i
c j=1
During each iteration of the outer loop, the inner loop is run once. Thus the time take by each iteration of the outer loop is
i
d+c j=1
where d is a constant. For Outer loop, the index variable ranges over [1, 2, 4, 8, · · · , 2n]. Thus the time taken by the algorithm is at most
which equals
i
[d+c] i∈{1,2,4,··· ,2n} j=1
d+ci i∈{1,2,4,··· ,2n } i∈{1,2,4,··· ,2n }
Note that the number of items in the set {1,2,4,··· ,2n} is n+1. Thus
i∈{1,2,4,··· ,2n }
d = d(n + 1)
c i = c(1 + 2 + 4 + 8 + 16 + · · · + 2n) i∈{1,2,4,··· ,2n }
This is a geometric progression with common ratio 2. The above sum equals c(2n+1 − 1). Thus the total time taken by the algorithm is d(n + 1) + c(2n+1 − 1) which is O(2n).
(d) i = n
while i >= 2 {
for j in range [1, i] {
}
i=i/2 }
5
Ans. Let c1 be the constant associated with the inner loop and c2 be the constant associated with the outerloop, and let c = max{c1, c2}. Each iteration of the inner loop takes time ≤ c. Thus the time taken for the inner loop is at most
i
c = ci j=1
For the outerloop, the index variable i ranges over {n,n/2,n/4,···2}. Thus the time take by the algorithm is at most
which equals
i∈{n,n/2,n/4··· ,2
ci i∈{n,n/2,n/4··· ,2
Thus summation is a geometric progression with a common ratio of 1/2. Thus thus summation is at most 2n. Thus the total time taken is at most 2cn which is O(n).
3. Consider the following two methods that compute the greatest common divisor of two positive
integers.
GCD_1(a, b) {
n = min(a, b); // min(a, b) returns the minimum of a and b
for (int i = n; i >=1; i–)
if both(a%i)and(b%i)arezero return i;
}
GCD_2(a, b) {
x = max{a, b}
y = min{a, b}
while (y != 0) {
z = x % y;
x = y;
y = z;
}
return x; }
(40 Points)
Write a Java program that implements both of the above methods. Play with the program by giving very large numbers as inputs to both the numbers. You do not need to submit your code. Submit the answers to the following questions.
6
ic
(a) Pick two 9-digit primes and run both methods. Report the actual execution time. Use https://primes.utm.edu/lists/small/millions/ for 9 digit primes.
(b) Pick two 10 digit primes and run both methods. Report the actual execution time. Use https://primes.utm.edu/lists/small/small.html for 10 digit primes.
You can use System.currentTimeMillis() to calculate the execution times.
(c) Derive the runtime of GCD 1 when inputs a and b are n-bit integers.
Ans. An n bit integer can have a maximum possible value of 2n. Thus the loop is performed in the worst-case 2n times. each iteration of the loop takes constant time. Min operation also takes constant time. Thus the time taken is O(2n).
(d) Show that the run-time of GCD 2 is O(n) when the inputs a and b are n-bit integers. Ans. We use the following crucial observation if u ≤ v, then u%v ≤ u/2. This is because isv>u/2,thendividingu%v=u−vandu−v≤u/2whenv>u/2. Ifv=u/2,then u%v=0. Ifv
}
Ans. O(n log n)
(b) x = n;
while (x >= 2) {
x= sqrt{x}; }
Assume that sqrt(x) takes constant time. Ans. O(loglogn).
8