Mathematical Approach to Measuring Running Times

Question 1

Is the cost of basic operations low or high

Answer 1

low

Question 2

formula for total running time exact mathematical models

Answer 2

sum of cost x frequency of all operations

Question 3

example of sum for a precise running time

Answer 3

T(N) = (number of iterationscost of that operation) + 9number of iterationscost of that operation)

eg. T(N) = (2cost of addition) + (8cost of subtraction)

Question 4

calculations are simplified using another type of modeling. Waht is it called

Answer 4

cost modelling

Question 5

disadvantages of precise mathematical calculations

Answer 5

running times change from computer to computer

tedious

need to know the exact cost of individual operations

Question 6

three types of cost models

Answer 6

all operations take a constant cost of 1

focus on highest order terms only

only count some operations

combination

Question 7

what to be careful of when only considering highest order terms in cost modelling

Answer 7

Make sure that the operations you are not counting add up to a
factor lower than the operations you do count

Question 8

when you have simplified a cost model how do you indicate it has been simplified

Answer 8

tilde notation ~ before