本次美国代写是一个计算性与复杂性相关的Problem Set
1. True or false. Explain why.
2. Rank the following functions in order from smallest asymptotic running time to largest. Additionally,
identify all pairs x; y where fx(n) = Θ(fy(n)).
3. What is the asymptotic runtime for each of the following algorithms for computing kn, where k is an
integer and n ≥ 1 is a power of 2?
Algorithm 1
1. Set x = k
2. Set i = 1
3. while ( i < n)
(a) x = k * x
(b) i = i + 1
4. return x
Algorithm 2
1. Set x = k
2. Set i = 1
3. while ( i < n)
(a) x = x * x
(b) i = 2 * i
4. return x
4. The Euclidean algorithm is used to find the greatest common divisor (gcd) between a pair of integers.
For example the gcd of 32 and 80 is 16. When the gcd of integers is 1 such as for 14 and 15, we say
that the integers are relatively prime. The gcd function is given two integers a and b and returns their
greatest common divisor.
gcd(a,b)
{
x = a
y = b
while (y not equal 0) {
r = x%y
x = y
y = r
}
return x
}
Show all your work for the following problems:
(a) Are 1274 and 10505 relatively prime?
(b) Are 7289 and 8029 relatively prime?
(c) Show the worst case time complexity of the Euclidean algorithm.
5. Challenge! Optional
void runTimeFun(int n){
for (int i = 1; i <= n; i++){
for (int j = 0; j < n; j += i) {
for (int k = 0; k < n ; k++) {
if (i % 2 == 0) {
for (int m = 1; m <= n ; m *= 2){
cout << m << endl;
}
} else {
cout << i << endl;
}
}
}
}
}
What is the worst case runtime analysis of runTimeFun? Show all your work