Recall the Academic Integrity statement that you signed. Write all answers clear
ID: 674464 • Letter: R
Question
Recall the Academic Integrity statement that you signed. Write all answers clearly on these pages, ensuring your final answers are easily recognizable. The number of points for each problem is clearly marked, for a total of 25 points. I will post my solutions on the web on Wednesday, off the Solutions link, after class. The following two functions each determine whether or not any two values in array a (storing N values) sum to v. As is shown in the Assume a fast qsort function and search does a binary search for its 3rd argument, returning whether or not it is in the array. bool sum_to_v (int all, int N, int v) for (int i=0; iExplanation / Answer
2)
As per Big O notation this is correct. f(n) = 15 is a constant function with no dependency on n.
since it is constant big o notation specifies that the value of the constant must be fixed and if they are fixed then it won't effect the function. so it will be O(1) as per big oh notation.
6)
10^6
time will be 1 * log2(10^6) = 6*log2(10) = 6*3.321 = 19.926
2nd part
10^6
= 20 * 10^6 * 19.926 (19.926 from above)
= 398.52 & 10^6
3rd part
1000 * 10^5 * 10^5 = 10^13
so in total it will take 10^13 to run.
7)
The fact is that the result and running time increase by logn times in comparison to nlogn.
As we can see from the result the difference is not that much
nlogn is almost 20 times more than n as per the size of the n.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.