Very simple problem here on big Oh Notation. Please label your ansers clearly. 1
ID: 662591 • Letter: V
Question
Very simple problem here on big Oh Notation. Please label your ansers clearly.
1. What is the time complexity of silly1 (give tightest big O)?
2. What is the time complexity of silly2 (give tightest big O)?
3. What is the time complexity of silly3 (give tightest big O)?
Codes are below:
----------------------------------------------------------------------------------------------------
public static void silly1(int n) {
for (int i = 0; i < n; ++i) {
int j = n;
while (j > 0) {
System.out.println("j = " + j);
j = j - 1;
}
}
}
public static void silly2(int n) {
for (int k = n; k > 0; k--) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j){
System.out.println("j = " + j);
}
}
}
}
public static void silly3(int n) {
for (int k = n; k> 0; k--){
System.out.println("k = " + k);
}
for (int h = 0; h < n; h++){
System.out.println("h =" + h);
}
}
Explanation / Answer
Part1:
The complexity of Silly1 is O(n^2)
Explaination: The outer loop runs for n times from i=0 to i=n-1 and for each of the i'th run the while loop runs for n times from j=n to j=1 So total Complexity : n*n =O(n^2)
Part 2:
The complexity of Silly2 is O(n^3)
Explaination: The outer loop runs for n times from k=n to k=1 and for each of the kth run the for loop runs for n times from i=0 to i=n-1 and for each of the i'th run the for loop runs for n times from j=0 to j=n-1 So total Complexity : n*n*n =O(n^3)
Part 3:
The complexity of Silly3 is O(n)
Explaination: The first loop runs for n times from k=n to k=1 and the second loop runs for n times from h=0 to h=n-1. So total Complexity : n+ n=2*n =O(n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.