CSCI 1301 Lecture Notes - Lecture 15: Time Complexity

26 views2 pages

Document Summary

Measuring the efficiency of an algorithm in terms of space (memory) and time (speed) Efficiency is expressed as a function of the input size. Generally look at worst case, longest time and most space used. Tends to be looked at as more important than space. Assume that each operation takes one unit of time to process. Complexity of loops example for num1 in range(0,n): for num2 in range(0,n): x = x+1. O(1) constant time the program always takes the same of time, regardless of the amount of data it"s working on. Example: looking for the smallest item in a sorted list. O(n) linear time the program get slower in proportion to the amount of data elements n searching for something by looking at all the items. O(n^2) quadratic time the program gets slower as a square of the amount of data elements n for each item, must look at all the other items each time a loop within a loop.

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