Running time The running time depends on the input:an already sorted sequence is easier to sort Parameterize the running time by the size of the input, since short sequences are easier to sort than long ones Generally, we seek upper bounds on the running time because every body likes a gu uarantee Day 1 Introduction to Algorithms L1.19Day 1 Introduction to Algorithms L1.19 Running time • The running time depends on the input: an already sorted sequence is easier to sort. • Parameterize the running time by the size of the input, since short sequences are easier to sort than long ones. • Generally, we seek upper bounds on the running time, because everybody likes a guarantee