Big O

Question 1

Best, worst, expected cases

Answer 1

Describe the big O (or big theta) time for particular inputs or scenarios

Question 2

Big O, big omega, big theta

Answer 2

Describe the upper, lower, and tight bounds for the runtime

Question 3

Add runtimes

Answer 3

If the algorithm is “do this, then do that”

Question 4

Multiply runtimes

Answer 4

If the algorithm is “do this for each time you do that”

Question 5

Amortized Time

Answer 5

Concept that takes into account the worst case happens every once in a while, but once it does it won’t happen again for so long that the cost is “amortized”

The motivation for amortized analysis is that looking at the worst-case run time per operation, rather than per algorithm, can be too pessimistic.

Example: If the insertion time takes O(2x), the amortized time for each insertion is O(1)

Question 6

.sort( )

Answer 6

Modifies the list it is called on in-place, runtime of O(n log n)

Question 7

sorted( )

Answer 7

Creates a new copy of the modified list in memory, does not modify the original list, primary difference is additional space complexity vs .sort( )

Question 8

Try/Except

Answer 8

A try statement may have more than one except clause, to specify handlers for different exceptions

Example:
while True:
… try:
… x = int(input(“Please enter a number: “))
… break
… except ValueError:
… print(“Oops! That was no valid number. Try again…”)
… except:
… print(“Don’t try this at home”)

Be wary of a last except: with nothing specified like above - the last except clause may omit the exception name(s), to serve as a wildcard. Use this with extreme caution, since it is easy to mask a real programming error in this way

Question 9

Big O

Answer 9

Measures how time scales with respect to some input variables

Question 10

O(1)

Answer 10

Constant time

Question 11

O(n)

Answer 11

Linear time

Question 12

O(n^2)

Answer 12

Quadratic time