CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Efficiency: Builtin Runtime Table
- General
- Strings
- Lists
- Sets
- Dictionaries
For a more complete list, see
here
| General |
| Function/Method |
Complexity |
Code Example |
| Print |
O(N) |
# where N is the size of the input
print(input) |
| Range in Iteration |
Number of iterations = (end - start)/step |
for i in range(start, end, step):... |
|
| Strings: s is a string with N characters |
| Function/Method |
Complexity |
Code Example |
| Len |
O(1) |
len(s) |
| Membership |
O(N) |
"a" in s |
| Get single character |
O(1) |
value = s[index] |
| Get slice |
O(end - start) |
s[start:end] |
| Get slice with step |
O((end - start)/step) |
s[start:end:step] |
| Chr() and Ord() |
O(1) |
chr(s)
ord(s) |
| Concatentation |
O(len(s1) + len(s2)) |
s3 = s1 + s2 |
| Character Type Methods |
O(N) |
s.isalnum()
s.isalpha()
s.isdigit()
s.islower()
s.isspace()
s.isupper() |
| String Edit Methods |
O(N) |
s.lower()
s.upper()
s.replace()
s.strip() |
| Substring Search Methods |
O(N) |
s.count()
s.startswith()
s.endswith()
s.find()
s.index() |
|
| Lists: L is a list with N elements |
| Function/Method |
Complexity |
Code Example |
| Len |
O(1) |
len(L) |
| Append |
O(1) |
L.append(value) |
| Extend |
O(K) |
# len(a) = K
L.extend(a) |
| Concatentation with += |
O(K) |
# len(a) = K
L += a |
| Concatentation with + |
O(N + K) |
# len(a) = K
L = L + a |
| Membership Check |
O(N) |
item in L |
| Pop Last Value |
O(1) |
L.pop() |
| Pop Intermediate Value |
O(N) |
L.pop(index) |
| Count values in list |
O(N) |
L.count(item) |
| Insert |
O(N) |
L.insert(index, value) |
| Get value |
O(1) |
value = L[index] |
| Set value |
O(1) |
L[index] = value |
| Remove |
O(N) |
L.remove(value) |
| Get slice |
O(end - start) |
L[start:end] |
| Get slice with step |
O((end - start)/step) |
L[start:end:step] |
| Sort |
O(N log (N)) |
L.sort()
sorted(L) |
| Multiply |
O(N*D) |
#where D is an int
A = L*D |
| Minimum |
O(N) |
min(L) |
| Maximum |
O(N) |
max(L) |
| Copy |
O(N) |
copy.copy(L) |
| Deep Copy |
O(N*M) |
# where L is a 2D list with N rows and M cols
copy.deepcopy(L) |
|
| Sets: s is a set with N elements |
| Function/Method |
Complexity |
Code Example |
| Len |
O(1) |
len(s) |
| Create Set from List |
O(N) |
set(lst) # N = len(lst) |
| Membership |
O(1) |
elem in s |
| Adding an Element |
O(1) |
s.add(elem) |
| Removing an Element |
O(1) |
s.remove(elem)
s.discard(elem) |
| Union |
O(len(s) + len(t)) |
s|t |
| Intersection |
O(min(len(s), len(t))) |
s&t |
| Difference |
O(len(s)) |
s - t |
| Clear |
O(len(s)) |
s.clear() |
| Copy |
O(len(s)) |
s.copy() |
|
| Dictionaries: d is a dictionary with N key-value pairs |
| Function/Method |
Complexity |
Code Example |
| Len |
O(1) |
len(d) |
| Membership |
O(1) |
key in d |
| Get Item |
O(1) |
value = d[key]
d.get(key, defaultValue) |
| Set Item |
O(1) |
d[key] = value |
| Delete Item |
O(1) |
del d[key] |
| Clear |
O(N) |
d.clear() |
| Copy |
O(N) |
d.copy() |