Identify the unit count for each portion of the code given below to identify the
ID: 3665877 • Letter: I
Question
Identify the unit count for each portion of the code given below to identify the overall Big Oh speed. Use the example below as a template for your answer, or some classes may use summations. The table answers below are NOT correct!! But the overall setup is. Partial credit will be given if some portion of the work shown is correct.
Code
Cost
# of Times
Total
int sum1(int N)
{
int s = 0;
for(int i = 1; i <= N; i++)
{
s = s + i;
}
return s;
}
-
-
1
1
1
-
-
1
1
1
1 (int i) + 1 (<=) + 1 (++)
1 + 2(n + 1)
2n + 3
-
-
2
n
2n
-
-
-
-
1
1
1
-
-
Final
4n + 6
O(n)
MAKE THE CHART FOR THESE:
1.)
sum = 0;
for( i = 1; i < n; i *= 2 )
for( j = 0; j < n; j++ )
++sum;
2.)
sum = 0;
for( i = 0; i < n; i++ )
for( j = 0; j < i * i; j++ )
for ( k = 0; k < j; k++ )
++sum;
Code
Cost
# of Times
Total
int sum1(int N)
{
int s = 0;
for(int i = 1; i <= N; i++)
{
s = s + i;
}
return s;
}
-
-
1
1
1
-
-
1
1
1
1 (int i) + 1 (<=) + 1 (++)
1 + 2(n + 1)
2n + 3
-
-
2
n
2n
-
-
-
-
1
1
1
-
-
Final
4n + 6
O(n)
Explanation / Answer
1)A good way of thinking about Big-O performance is to pretend each element of the code is a mathematical function that takes in n items and returns the number of computations performed on those items.
For example, a single for loop like for ( i = 0; i < n; i++ ) would be equivalent to a function i(), where i(n) = n, indicating that one computation is performed for each input n.
If you have two nested loops, then the functional equivalent for
would look like these two functions:
Working these two functions out produces an end result of n*n = n^2, since j(n) can be substituted for n.
What this means is that as long as you can solve for the Big-O of any single loop, you can then apply those solutions to a group of nested loops.
For example, let's look at your second problem:
i+=2 means that for an input set of n items (n0, n1, n2, n3, n4) you're only touching every other element of that set. Assuming you initialize so that i=0, that means you're only touching the set of (n0,n2,n4). This means you're halving the size of the data set that you're using for processing, and means the functional equivalents work out like:
Solving these gets you (n/2) * n = (n^2)*(1/2). Since this is Big-O work, we remove the constants to produce a Big-O value of (n^2).
The two key points to remember here:
Big-O math starts with a set of n data elements. If you're trying to determine the Big-O of a forloop that iterates through that set of n elements, your first step is to look at how the incrementor changes the number of data elements that the for routine actually touches.
Big-O math is math. If you can solve for each for expression individually, you can use those solutions to build up into your final answer, just like you can solve for a set of equations with common definition.
No, it is not O(4).
A better way to see this is to count how many times the loop executes(in fact, that is what the code is doing).
sum(sum(sum(1, k=0..j), j=0..i*i), i=0..n)
= sum(sum(j,j=0..i*i),i=0..n) = sum(i*i*(i*i+1)/2,i=0..n) which is on the order of sum(i^4, i=0..n) which is on the order of n^5.
Essentially because the middle loop is i*i and is being executed for each of the inner most loop it needs to be counted an extra time.
In C++
http://codepad.org/nKJ9IUnt
You can use this table and compute the finite differences(taking derivatives) until the result is a constant or 0. You'll find that it takes 5 derivatives to have a constant list. This means that it the list is on the order of n^5.
e.g., If we had a list where each difference between two elements were a constant then the list could be represented by a linear function. If the difference of the difference was constant then it would be a quadradic, etc. (it doesn't matter about the lower order terms because they get translated by the derivative/difference)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.