Results 1 to 6 of 6
Thread: Analysis of Algorithms
 03292013, 08:45 AM #1Member
 Join Date
 Feb 2013
 Posts
 32
 Rep Power
 0
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
 03292013, 09:28 AM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,525
 Blog Entries
 7
 Rep Power
 20
Re: Analysis of Algorithms
That is Horner's rule: for a polynomial a(n)*x^(n) +a(n1)*x^(n1) + ... a(0), the polynomial can be rewritten as: x*(a(n)*x^(n1) ... a(1))+a(0). If you recursively apply this rule to the polynomial (of lower degree) you can see that it takes n1 multiplications and n1 additions to evaluate the entire polynomial.
kind regards,
Joscenosillicaphobia: the fear for an empty beer glass
 03292013, 06:17 PM #3Member
 Join Date
 Feb 2013
 Posts
 32
 Rep Power
 0
Re: Analysis of Algorithms
Hmm, interesting and thank you. I am still having trouble finding how many additions and multiplications total.
 03292013, 06:37 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,525
 Blog Entries
 7
 Rep Power
 20
Re: Analysis of Algorithms
Erm, I gave the answer already.
kind regards,
Joscenosillicaphobia: the fear for an empty beer glass
 03292013, 07:03 PM #5Member
 Join Date
 Feb 2013
 Posts
 32
 Rep Power
 0
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!
 03292013, 07:47 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,525
 Blog Entries
 7
 Rep Power
 20
Similar Threads

Analysis of Command Line
By rem7600 in forum Forum LobbyReplies: 1Last Post: 04102012, 06:46 PM 
HELP with code analysis
By geenah in forum New To JavaReplies: 4Last Post: 11182011, 07:59 PM 
boxcounting analysis problem
By sbrentphysics in forum Advanced JavaReplies: 2Last Post: 04082011, 09:38 PM 
Temperature analysis program
By Evii0 in forum New To JavaReplies: 8Last Post: 03292011, 09:05 AM 
NetBeans Profiler and memory analysis
By soheil in forum Advanced JavaReplies: 0Last Post: 08022009, 05:32 PM
Bookmarks