Determine the order of magnitude for each piece of code. 1 additional bonus poin
ID: 3887267 • Letter: D
Question
Determine the order of magnitude for each piece of code. 1 additional bonus point for giving the precise Big O. When giving precise Big O you can exclude the looping structures from the statement. You should take them into consideration only to determine the number of times the inner part runs. Sample#1: int i = 0; int j = 1; Sample #2: for(int i = 0; i < n; i++){ sum += i; } int j = 0; while(j < n){ sum--; j++; } Sample #3: for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ sum += i; sum -= (j + 1); } } Sample #4: for (int i = 0; i < n; i++) { sum += i; } for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { sum--; } }
Explanation / Answer
Sample#1:
int i = 0; => O(1)
int j = 1; => O(1)
Sample #2:
for(int i = 0; i < n; i++) //this full block runs O(n) time
{
sum += i; => O(n)
}
int j = 0; => O(1)
while(j < n) //this full block runs O(n) time
{
sum--; => O(n)
j++; => O(n)
}
Overall : O(n)
Sample #3:
for(int i = 0; i < n; i++) => //this full block runs O(n) time
{
for(int j = 0; j < n; j++) => //this full block runs O(n) time
{
//this full block runs O(n*n) times because of nested loop
sum += i; =>O(n*n)
sum -= (j + 1); =>O(n*n)
}
}
Overall : O(n*n) or O(n2)
Sample #4:
for (int i = 0; i < n; i++) //this full block runs O(n) time
{
sum += i; => O(n)
}
for (int j = 0; j < n; j++) //this full block runs O(n) time
{
for (int k = 0; k < n; k++) //this full block runs O(n) time
{
sum--; => O(n*n)
}
}
Overall : O(n*n) or O(n2)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.