Results 1 to 6 of 6
  1. #1
    rhym1n is offline Member
    Join Date
    Feb 2013
    Posts
    32
    Rep Power
    0

    Default Analysis of Algorithms

    I haven't taken a programming class yet and this question really confuses me, any help is greatly appreciated.

    The following pseudocode procedure can be used to evaluate the polynomial 8 – 10x + 〖7x〗^2 - 〖2x〗^3 + 〖3x〗^4 + 〖12x〗^5, when x is replaced by an arbitrary (but fixed) real number r. For this particular instance, n = 5 and a_0 = 8, a_1 = -10, a_2 = 7, a_3 = -2, a_4 = 3, and a_5 = 12.
    Java Code:
    	procedure PolynomialEvaluation1
    	  (n: nonnegative integer;
    	   r, a_0, a_1, a_2,…, a_n: real)
    	begin
    	   product := 1.0
    	   value := a_0
    	   for i := 1 to n do
    	      begin
    	         product := product * r
    	         value := value + a_i * product
    	      end
    	end
    How many additions take place in the evaluation of the given polynomial? (Do not include the n – 1 additions needed to increment the loop variable i.) How many multiplications?

  2. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,431
    Blog Entries
    7
    Rep Power
    20

    Default Re: Analysis of Algorithms

    That is Horner's rule: for a polynomial a(n)*x^(n) +a(n-1)*x^(n-1) + ... a(0), the polynomial can be rewritten as: x*(a(n)*x^(n-1) ... a(1))+a(0). If you recursively apply this rule to the polynomial (of lower degree) you can see that it takes n-1 multiplications and n-1 additions to evaluate the entire polynomial.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    rhym1n is offline Member
    Join Date
    Feb 2013
    Posts
    32
    Rep Power
    0

    Default Re: Analysis of Algorithms

    Hmm, interesting and thank you. I am still having trouble finding how many additions and multiplications total.

  4. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,431
    Blog Entries
    7
    Rep Power
    20

    Default Re: Analysis of Algorithms

    Erm, I gave the answer already.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    rhym1n is offline Member
    Join Date
    Feb 2013
    Posts
    32
    Rep Power
    0

    Default Re: Analysis of Algorithms

    Oh sorry. I read that as soon as I woke up and things didn't click lol. My bad.

    Thank you again!

  6. #6
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,431
    Blog Entries
    7
    Rep Power
    20

    Default Re: Analysis of Algorithms

    Quote Originally Posted by rhym1n View Post
    Oh sorry. I read that as soon as I woke up and things didn't click lol. My bad.

    Thank you again!
    You're welcome and the only things that click when I wake up are the on/off switch of my espresso machine and my llghter for my first sigaret of the day ;-)

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Analysis of Command Line
    By rem7600 in forum Forum Lobby
    Replies: 1
    Last Post: 04-10-2012, 06:46 PM
  2. HELP with code analysis
    By geenah in forum New To Java
    Replies: 4
    Last Post: 11-18-2011, 07:59 PM
  3. boxcounting analysis problem
    By sbrentphysics in forum Advanced Java
    Replies: 2
    Last Post: 04-08-2011, 09:38 PM
  4. Temperature analysis program
    By Evii0 in forum New To Java
    Replies: 8
    Last Post: 03-29-2011, 09:05 AM
  5. NetBeans Profiler and memory analysis
    By soheil in forum Advanced Java
    Replies: 0
    Last Post: 08-02-2009, 05:32 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •