1. Big-Oh and Run Time Analysis: Describe the worst case running time of the fol
ID: 3881724 • Letter: 1
Question
1. 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.
e) void silly(int n, int x, int y) {
if (x < y) {
for (int i = 0; i < n; ++i)
for (int j = 0; j < n * i; ++j)
System.out.println(”y = ” + y);
} else {
System.out.println(”x = ” + x);
}
} __________________
f) void silly(int n) {
j = 0;
while (j < n) {
for (int i = 0; i < n; ++i) {
System.out.println(”j = ” + j);
}
j = j + 5;
}
} __________________
g) void silly(int n) {
for (int i = 0; i < n * n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < i; ++k)
System.out.println(”k = ” + k);
for (int m = 0; m < 100; ++m)
System.out.println(”m = ” + m);
}
}
} __________________
h) 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);
}
} __________________
i) 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;
}
o(n). o(n3 log n)·0(n log n). O(n). O(n2 log n). 0(ns), 0(29. 0(r). 0(log n), 0(1), 0(n4), O(nn)Explanation / Answer
Solution:
e)
In the given code snippet there are two loops which are nested
the outer loop is running n number of times
and
the inner loop is running n * i number of times
so total running time will be
at i = 1, j will run n times
at i = 2, j will run 2n times
at i = 3, j will run 3n times
.
.
.
at i = n, j will run n*n times
adding up
n+2n+3n+....n*n
n(1+2+3+4+5+.....+n) = n * (n(n+1)/2) = O(n^3)
So the time complexity will be
T(n) = O(n^3)
f)
In this code snippet as well there are two loops which is nested one is while loop and another is for loop.
while loop(the outer loop) is running n/5 number of times
and inner loop(the for loop) is running n number of times
so total run is n*n/5 = O(n^2)
So, the time complexity is
T(n) = O(n^2)
g)
Here three loops are nested
the top most is running n^2 number of times
the middle one is running n number of times
and the last loop is running i number of times
there is one more loop there but it is iterating 100 times each so that will be considered as constant considering all the runtime the loop is running n^4 times.
So, time complexity
T(n) = O(n^4)
h)
Here two loops are nested the loop with the variable m is running 5000 number of times which will be considered as constant
because in computational complexity terms n is always considered to be very large
so, the outer loop is running n^2 number of times
and inner loop is running n number of times
so, time complexity
T(n) = O(n^3)
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.