Need help

This is a discussion on Need help within the C Programming forums, part of the General Programming Boards category; hi all... i gotsome problems.. I don't understand what it means at all... "write a function pread that reads in ...

  1. #1
    Registered User
    Join Date
    Oct 2009
    Location
    Indonesia
    Posts
    68

    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. #2
    Registered User
    Join Date
    Mar 2010
    Posts
    6
    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. #3
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    Quote Originally Posted by Kinshara View Post
    "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. #4
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,831
    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 subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21