CSCC73H3 Lecture : Time complexity of algorithms

61 views3 pages
19 Oct 2011
School
Course

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 .

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