Question 967747: Suppose you have the following sequence of runtime for an operation: 3, 6, 11, 18, 27, 38,...
• List the next 2 elements in the sequence.
• Determine the general equation that yields results for any element of the sequence.
• What is the runtime for matrix multiplication operations in terms of big-O notation?
I am really lost on how to do this. Please send help. SOS. Thank You
Answer by rothauserc(4718)   (Show Source):
You can put this solution on YOUR website! For the given series
3, 6, 11, 18, 27, 38
first differences between numbers in series
3, 5, 7, 9, 11
second differences from first differences is
2, 2, 2, 2
we have a geometric series of order 2, that is
n^2
**************************************************
return to original sequence
3 6 11 18 27 38
n^2 terms for nth term are
1 4 9 16 25 36
differences is are
2 2 2 2 2 2
******************
This must mean that the rule to find any nth term in this sequence is;
n^2 +2
*******************
now we can answer the questions
*******************************
1) the next two numbers in the sequence are
7^2 +2 = 51
8^2 +2 = 66
the next two numbers are 49, 66
**********************************
2) n^2 + 2
**********************************
3) take multiplying two n x n matrices, then
there are n^2 elements in the output matrix, that would require
n*n^2 = n^3 operations to compute the entire matrix - that is, the
speed of the most straightforward algorithm is O(n^k), where k = 3.
|
|
|
