# Thread: Need help

1. ## Need help

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!!

2. 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.

3. Originally Posted by Kinshara
"write a function pread that reads in n pairs of coeffients and exponents... show that this operation can be peformed in O(n) time!!!"
I highly doubt that is what the question is. Maybe posting the exact question, verbatim, would help clear things up.

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.

4. So for n=3
Code:
10 2
7 5
1 8
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.

Popular pages Recent additions