Description
1. In the definition of Big-O, why is the “for N >= n0” needed?
Time complexity is asymptotic. So, considering when n approach infinity, we need require “N >= n0”, which means time complexity is always stable for all values after n0.
6 pts
2. If f1(N) = 2N and f2(N) = 3N, why are they both O(N), since 3N is larger than 2N for N>=1?
Recording to the definition of Big O, T(N) = O(f(N)) means that T(N) <= cf(N) for some constant c and for N >= n0, and f1(N) = 2N <= cN, f2(N) = 3N <= cN for some constant c when N >= 1. So, they are both O(N).
6 pts
3. a) For f1(N) = 2N and f2(N) = 3N:
calculate f1(5) and f2(5), then f1(10) and f2(10). When N was doubled in each case, what happened to the result?
f1(5) = 10, f2(5) = 15,
f1(10) = 20, f2(10) = 30,
When N was doubled in each case, the result became double.
b) For f1(N) = 2N*N and f2(N) = 3N*N:
calculate f1(5) and f2(5), then f1(10) and f2(10). When N was doubled in each case, what happened to the result?
f1(5) = 50, f2(5) = 75,
f1(10) = 200, f2(10) = 300,
When N was doubled in each case, the result became quadruple.
6 pts
4. Since Big-O notation is a mathematical tool for functions like f(N) or g(N), how is it applicable to algorithm analysis?
Algorithm analysis is dedicated to understanding the complexity of algorithms that could be expressed by Big-O. And Assume two functions f(N) and g(N) are considered as two algorithms, as the scale of the problem(n) increases, O(f(n)) and O(g(n)) are their own growth rates of algorithm execution time. In the meantime, if there exists O(f(n)) < O(g(n)), which means complexity of algorithm g(n) is more than complexity of algorithm f(n). So Big-O could be applicable to algorithms analysis.
6 pts
5. Which grows faster, 2^n or n! ? Explain why.
n! grows faster.
Justification:
Prove by induction:
Base case: n = 4, 2^4=16 < 4!=24
So, it is true for n = 1.
Induction step: Assume it is true for k, that 2^k < k!
Show true for k+1:
2^(k+1) = 2^k * 2
(k+1)! = k! * (k+1)
Due to 2^k < k! and 2 < k+1, so 2^(k+1) < (k+1)!
Conclusion: by induction, the statement holds true for all n >= 4.
So n! grows faster when n >= 4.
10 pts (2 each)
6. Give the Big-O notation for the following expressions:
a. 4n^5 + 3n^2 – 2 O(n^5)
b. 5^n – n^2 + 19 O(5^n)
c. (3/5)*n O(n)
d. 3n * log(n) + 11 O(n*log(n))
e. [n(n+1)/2 + n] / 2 O(n^2)
Questions 7-12 are 10 points each.
Assume numItems has the role of N, which may vary from one run to the next.
7. What is the Big-O running time for this code? Explain your answer.
for (int i=0; i<numItems; i++)
System.out.println(i+1);
int i=o, i < numItems; i++; // 1 + (n+1) + n
// 1 + (n+1) + n = 2n + 2, so the result is O(n).
8. What is the Big-O running time for this code? Explain your answer.
for (int i=0; i<numItems; i++)
for (int j=0; j<numItems; j++)
System.out.println( (i+1) * (j+1) );
int i=0; i<numItems; i++; // 1 + (n+1) + n
int j=0; j<numItems; j++; // n*(1 + (n+1) + n)
(i+1) * (j+1); // n*n*3
// 1 + (n+1) + n + n*(1 + (n+1) + n) + n*n*3 = 5*n^2 + 4n + 2, so the result is O(n^2).
9. What is the Big-O running time for this code? Explain your answer.
for (int i=0; i<numItems+1; i++)
for (int j=0; j<2*numItems; j++)
System.out.println( (i+1) * (j+1) );
int i=0; i<numItems+1; i++; // 1 + (n+2) + (n+1)
int j=0; j<2*numItems; j++; // (n+1)*(1 + (2n+1) + 2n)
(i+1) * (j+1); // (n+1)*2n*3
// 1 + (n+2) + (n+1) + (n+1)*(1 + (2n+1) + 2n) +(n+1)*2n*3 = 10*n^2 + 14n + 6, so the result is O(n^2).
10. What is the Big-O running time for this code? Explain your answer.
if ( num < numItems )
for (int i=0; i<numItems; i++)
{
System.out.println(i);
}
else
System.out.println(“too many”);
When num < numItems:
num < numItems; // 1
int i=0; i<numItems; i++; // 1 + (n+1) + n
i; // n
1 + 1 + (n+1) + n + n = 3n + 3, so the result is O(n)
When num > numItems:
“too many”; // 1
So the result is O(1).
11. What is the Big-O running time for this code? Explain your answer.
int i = numItems;
while (i > 0)
i = i / 2; // integer division will eventually reach zero
i = numItems; // 1
i > 0; // lgn +1
i = i / 2; // lgn
1 + lgn + 1 + lgn = 2 + 2lgn, so the result is O(lgn)
12. What is the Big-O running time for this code? Explain your answer.
(You do not need to work out a recurrence formula).
public static int div(int numItems)
{
if (numItems == 0)
return 0;
else
return numItems%2 + div(numItems/2);
}
numItems == 0; // 1 + lgn
return 0； // 1
numItems%2 + div(numItems/2) // 2lgn
1 + lgn + 1 + 2lgn = 3lgn + 2, so the result is O(lgn).
Submit these files:
hw2.doc (.doc can be .txt, .jpg, etc.)