For each C++ function below, give the tightest asymptotic upper bound that you c
ID: 3747372 • Letter: F
Question
For each C++ function below, give the tightest asymptotic upper bound that you can determine for the function’s runtime, in terms of the input parameter. Where prompted, also compute the return value of the function.
(a)
int mangosorbet(int n) {
int q;
if (n > 2673)
q = 12000;
else
q = 6000;
while (q < 24000)
q++;
return 2 * n * n * n;
}
Return value of a:
Running time of a:
(b)
int pecanpie(int n) {
int i = 0;
int j = 8 * n;
while (j > 1) {
j = j / 2;
i++;
}
for (int k = 0; k < i * i; k++) {
j++;
}
return 3 * i;
}
Return value of b:
Running time of b:
(c)
int tootsieroll(int n) {
int s = 0;
for (int i = 0; i <= n; i++) {
if (i % 2 == 1)
s += i;
}
return s;
}
Return value of c:
Running time of c:
(d)
int sweetgeorgiabrown(int n) {
int j = 0;
for (int k = 1; k <= n; k++)
j = j + (mangosorbet(k) / k);
for (int m = 1; m < j; m++)
cout << "I am having so much fun with asymptotics!" << endl;
return n + (n % 41);
}
Running time of d:
(e)
int rainbowsprinklemintchocolatechipicecreamsandwich(int n) {
int j = 0;
for (int k = 0; k < n; k++)
j = mangosorbet(k);
return pecanpie(mangosorbet(n));
}
Running time of e:
Explanation / Answer
Return value of a: 5
Running time of a: .7
Return value of b: 8
Running time of b : 10
Return value of c : 6
Running time of c : 9
Return value of d: 7
Running time of e: 15
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.