Determine the precise (i.e., not just the order of magnitude) Big-Oh values for
ID: 3742549 • Letter: D
Question
Determine the precise (i.e., not just the order of magnitude) Big-Oh values for each of the following code samples, based on the number of statement executions. Your answers should be in the form of a Big-Oh polynomial (e.g., O(3N2 + 7N + 6)).
A) for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
sum += i;
}
}
B)
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
sum += i;
}
}
C)
for (int i = 0; i < n; i++)
{
sum += i;
}
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
sum--;
}
}
D)
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
for (int k = j; k < n; k++)
{
sum += j;
}
}
}
Explanation / Answer
Sample #1:
Solution:
Statement
# of times executed (general)
Actual # of times executed (N = 10)
Comments
int i = 0;
1
1
Assigning the values to the variable.
int j = 1;
1
1
Assigning the values to the variable.
Big-Oh:
O (2)
2
Addition of all the terms.
Sample #2:
Solution:
Statement
# of times executed (general)
Actual # of times executed (N = 10)
Comments
int i = 0;
1
1
The assignment statement .
i< n
N+1
11
Conditional statement, run for N times plus 1 time to break the loop.
sum += i;
N
10
The statement will execute for N time.
i++
N
10
The statement will execute for N times.
int j = 0;
1
1
The assignment statement .
while (j < n)
N
10
The Loop will execute for N times.
sum--;
N
10
The statement will execute for N times.
j++;
N
10
The statement will execute for N times.
Big-Oh:
O(6N + 3)
63
Addition of all the terms.
Sample #3:
Solution:
Statement
# of times executed (general)
Actual # of times executed (N = 10)
Comments
int i = 0;
1
1
The assignment statement .
i < n
N+1
11
Conditional statement, run for N times plus 1 time to break the loop.
sum += i;
N
10
The statement will execute for N time.
i++
N
10
The statement will execute for N times.
int j = 0;
1
1
The assignment statement .
j < n;
N+1
11
Conditional statement, run for N times plus 1 time to break the loop.
int k = 0;
N
10
The assignment statement .
k < n;
N2 +N
110
Conditional statement, run for N2 plus N times plus 1 time to break the loop.
sum--;
N2
100
The statement will execute for N*N times.
k++
N2
100
The statement will execute for N2 times.
(k loop jump) for( ; ;)
N2
100
Same as previous statement.
j++
N
10
The statement will execute for N times.
(j loop jump) for( ; ;)
N
10
Same as previous statement.
Big-Oh:
O(4N2+8N+4)
484
Addition of all the terms.
Sample #4:
Solution:
Statement
# of times executed (general)
Actual # of times executed (N = 10)
Comments
int i = 0;
1
1
The assignment statement
i < n
N+1
11
Conditional statement, run for N times plus 1 time to break the loop.
int j = i
N
10
Assignment i to j.
j < n
N2 +N
110
The complexity for running the two loops is N * N times.
int k = j
N2
100
Assignment operation.
k < n
N3 + N2
1100
The complexity for running the three loops is N * N *N times.
sum +=j
N3
1000
The statement will execute for N*N*N times.
k++
N3
1000
The statement will execute for N3 times.
(k loop jump) for( ; ;)
N3
1000
Same as previous statement.
j++
N2
100
The statement will execute for N2 times.
(j loop jump) for( ; ;)
N2
100
Same as previous statement.
i++
N
10
The statement will execute for N times.
(i loop jump) for( ; ;)
N
10
Same as previous statement.
Big-Oh:
O(4N3+5N2+5N+2)
4552
Addition of all the terms.
Statement
# of times executed (general)
Actual # of times executed (N = 10)
Comments
int i = 0;
1
1
Assigning the values to the variable.
int j = 1;
1
1
Assigning the values to the variable.
Big-Oh:
O (2)
2
Addition of all the terms.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.