CISC 235 Lecture Notes - Lecture 4: Reverse Polish Notation, Infix Notation, Operand

123 views12 pages

Document Summary

Let"s look at a simple example of determining the theta classification of a problem. First, we can observe that any algorithm that solves this must at the very least read or otherwise receive the values of x and the n+1 coefficients. Thus we can easily see that every algorithm for this problem must be in omega(n). Consider the simple algorithm i will call bfi_poly: Bfi_poly(x,c[n] c[0]): value = c[0] for i = 1. N: power = 1 for j = 1 i: power *= x value += c[i]*power return value time (you should verify this if it is not already familiar) This is where algorithm (and data-structure) designers start to get excited. It turns out that for this problem we can decrease the upper bound by finding a better algorithm - namely, horner"s rule: Horners_poly(x,c[n] c[0]): value = c[n] for i. = n-1 0: value = value*x + c[i] return value.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents

Related Questions