CSCC73H3 Lecture : Time complexity of algorithms
Document Summary
The worst-case time complexity of an algorithm is expressed as a function. T : n n where t (n) is the maximum number of steps in any execution of the algorithm on inputs of size n. Intuitively, the amount of time an algorithm takes depends on how large is the input on which the algorithm must operate: sorting large lists takes longer than sorting short lists; multiplying huge matrices takes longer than multiplying small ones. Note that an algorithm might take di erent amounts of time on inputs of the same size. We have de ned the worst-case time complexity, which means that we count the maximum number of steps that any input of a particular size could take. For example, if the time complexity of an algorithm is 3 n2, it means that on inputs of size n the algorithm requires up to. To make this precise, we must clarify what we mean by input size and step .