Data Structures and Algorithm Midterm Due 9AM 21 April 2018 1. True/False T/F Tw

Question

Data Structures and Algorithm Midterm Due 9AM 21 April 2018 1. True/False T/F Two different algorithms with the same big-O time complexity (assume O(n)) wl run in exactly same number operations, if you give them the same size input. By the definition of big-O, if f(n) O(n), we can also say that f(n)-o(m2) If two algorithms' time complexities are O(n2) and O(n), it might be the case that the one with O(n 2) time complexity runs in fewer operations for small sizes of n. 2. Definition: TIN) = 0?(M) if there are positive constants c and n0 such that T(N)s cf (N) when Based on the above definition of big-O and for fin)-5n 2+10n O(nA2), show example values of c and n0 that will satisfy f(n) sc'nA2 when n 2 no. If an algorithm takes 2 seconds for input size 64 (2A6), how long will it take for an input size 1024 (2A10) if the worst case running time complexity of the algorithm is the following? 3. b. ?. d. O(n) 0(n^2) O(logion) 4. Find the Big-O running time of the following code fragments. b. for(int i-o i

Explanation / Answer

1. False, Depending on the algorithm the operations performed also changes.

2.Show 5n2 + 10n = O(n2).
We need to find c and n0 such that:

5n2 + 10n <= cn2 for all n >= n0 .

Divide both sides by n2, getting:

5 + 10/n <= c for all n >= n0 .

If we choose n0 equal to 1, then we need a value of c such that:

5+10 <= c

We can set c equal to 16. Now we have:

5n2 + 10n <= 16n2 for all n >= 1 .

3. Ans: 0(n^2)

We have,

f(n) = n

4a. for (int j=n-1000; j<n; j++) {  // runs n times

for (int k=n/2; k<n; k++ ) { // same reasoning as 1. n^2

sum++;
}
}

Answer: N × N2 = O(N^3)

4b. for(int i=0; i<n; i++){  // runs n times
if(i>500) break;
sum++;
}?

Answer: O(N)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.