hi all... i gotsome problems.. I don't understand what it means at all...
"write a function pread that reads in n pairs of coeffients and exponents, 0<=i<n
of a polynomial, x. assume that expon i+1 > expon i, 0<=i<n-2, and that coef i != 0, 0<=i < n. show that this operation can be peformed in O(n) time!!!"
I really confuseeeeeeeeeeee... HELP!!
A polynomial is an expression like :
3x^2 + 4y
The coefficients are the integer parts, meaning 3, 4 here and the exponent is 2 (3x^2).
So, you should read those pairs and then prove that if the exponentials decrease and the coeffs are not 0 and between 0 and n (num of pairs), the operation is of linear complexity. Meaning that it grows just as n grows.
Hope that helps a bit. Maybe somebody else who is a mathematician can probably explain it better.
I highly doubt that is what the question is. Maybe posting the exact question, verbatim, would help clear things up.
Originally Posted by Kinshara
Also, what is the operation? It only says write a function that reads n "somethings" (what "somethings" is does not matter at all, in the exact question above). It does not say what to do with the n things after it reads them in. So the only operation is reading n "things" which, of course, takes O(n)-time. Hopefully you see that the question is ambiguous and incomplete now.
So for n=3
would meet the criteria that each successive exponent is greater than the previous.
10x^2 + 7x^5 + 1x^8
If all that is asked for is to read such a pair-wise value file, then of course it's linear time. The problem does not say you need to calculate the result.