What is the Big-Oh of this code **and** why? int n = 100; for (int counter = 0;
ID: 3737159 • Letter: W
Question
What is the Big-Oh of this code **and** why?
int n = 100;
for (int counter = 0; counter < n; counter++) {
// do something
}
What is the Big-Oh of this code **and** why?
int n = 100;
for (int counter = 0; counter < n; counter++) {
for (int index = 0; index < n; index++) {
// do something
}
}
What is the Big-Oh of this code **and** why?
int n = 100;
for (int counter = 0; counter < n; counter++) {
for (int index = 0; index < n/2; index++) {
// do something
}
}
What is the Big-Oh of this code **and** why?
int n = 100;
for (int counter = 0; counter < n; counter++) {
for (int index = n; index > 0; index/=2) {
// do something
}
}
Explanation / Answer
Solution
1) Big Oh of this loop will be O(n) because the loop executes n times since n = 100, so O(n) = O(100)
2) In this question there are two loops, the 2nd loop is nested inside the first loop's body. So for every iteration of the 1st loop, the 2nd loop will iterate n times. Hence Big Oh is O(n*n) = O(n^2) = O(100^2)
3) In this loop, the outer loop will execute n times and for every execution of the outer loop, the inner loop will execute n / 2 times. So Big Oh is O(n * n / 2) = O(100 * 100 / 2) = O(5000).
4) In this loop, the outer loop will run n times and the inner loop will run 2*log(n) + 2 hence Big Oh is O(n * 2 log(n) + 2)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.