C++ Determine the running times predicted by the detailed model of the computer
ID: 3599239 • Letter: C
Question
C++
Determine the running times predicted by the detailed model of the computer for the following program fragments:
Int Sum (int x, int n)
{
int sum = 0;
for ( int i = 0; i <= n; ++i)
sum = sum *x +1;
return sum;
}
Repeating question 2, using the simplified model of the computer.
Solve the recurrence relation T(n) = 2T(n/2) +1 given that T(1) = 1.
Using the definition of Big O, show that T(n) = 3n2+5n +2 is O(n2)
What is copy constructor? How to use it?
Which grows faster: n*log(n) or n2.
Choose a member function in the Unsorted and Sorted List (Array based and LinkedList based) that we discussed in class. Use diagram or pseudocode to explain how it works and how to implement.
Be able to write recursive function for a given problem.
Explanation / Answer
Determine the running times predicted by the detailed model of the computer for the following program fragments:
Int Sum (int x, int n)
{
int sum = 0; ==> This line runs for 1 time
for ( int i = 0; i <= n; ++i) ==> This line runs for n+ 1 time, one extrs time because when i = n+1 for loop condition fails
sum = sum *x +1;==> This line runs for n time
return sum;===> This line runs for 1 time
}
T(n) = n +1 + n + 1 + 1
=> O(n)
Overall time complexity is O(n)
Repeating question 2, using the simplified model of the computer.
Solve the recurrence relation T(n) = 2T(n/2) +1 given that T(1) = 1.
We can solve it using Masters method , T(n) is of the form T(n) = aT(n/b) + f(n)
a = 2, b = 2 and f(n) = 1 , So
g(n) = nlogb a => nlog 22 => => n1 , we can see that g(n)>= f(n) By case 1 of masters theorem we get
T(n) = O(n)
Using the definition of Big O, show that T(n) = 3n2+5n +2 is O(n2)
Answer: f(n) = 3n2+5n +2
We know that if f(n) = O(g(n)) then c*g(n) >=f(n) if there exists c and n0 such that n > n0
Let g(n) = 4n2 , we can clearly see that 4n2 >= 3n2+5n +2 , This we can write
f(n)= O(n2)
Which grows faster: n*log(n) or n2.
Answer: n2 grows faster
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.