Big-Oh and Run Time Analysis: Describe the worst case running time of the follow
ID: 3882312 • Letter: B
Question
Big-Oh and Run Time Analysis: Describe the worst case running time of the following pseudocode functions in Big-Oh notation in terms of the variable n.
a)void happy(int n) {
for (int i = n*n; i > 0; i--) {
for (int k = 0; k < n; ++k)
System.out.println(”k = ” + k);
for (int j = 0; j < i; ++j)
System.out.println(”j = ” + j);
for (int m = 0; m < 5000; ++m)
System.out.println(”m = ” + m);
}
} __________________
b) Consider the following function:
int mystery(int n) {
int answer;
if (n > 0) {
answer =(mystery(n-2)+3*mystery(n/2) + 5);
return answer;
}
else
return 1;
}
Write down the complete recurrence relation, T(n), for the running time of
mystery(n). Be sure you include a base case T(0). You do not have to
actually solve this relation, just write it down.
______________________________________________________
______________________________________________________
Explanation / Answer
Question 1:
I have written time complexity for each step. At last I have written overall complexity.
void happy(int n) {
for (int i = n*n; i > 0; i--) // This loop runs for n^n time = O(n^n)
{
for (int k = 0; k < n; ++k) // This loop runs for n times = O(n)
System.out.println(”k = ” + k);
for (int j = 0; j < i; ++j) // This loop runs for n^n(n^n+1)/2 times=O(n^n)
System.out.println(”j = ” + j);
for (int m = 0; m < 5000; ++m)// This loop runs for 5000 times which is constant
System.out.println(”m = ” + m);
}
}
Total Complexity:
n^n(n(n^n(n^n+1)/2)) it is equivalent to n^n(n(n^2n))
= n^n(n^3n) = n^4n
If we ignore constant because Big - Oh notation does not contains any constant.
Answer = O(n^n)
Question 2:
Recurrence relation:
T(n) = T(n-2) + 3*T(n/2) + 5
Here if we substitute n=0 then
T(0) = T(-2) + 3T(0) + 5
The program returns 1 if (n <= 0)
T(0) = 1 + 3*1 + 5 = 9
So T(0) = 9
Question 2:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.