This is just a PSA: Just saying "Runtime: O(n) Space: O(1)" IS NOT COMPLEXITY ANALYSIS!

This is just stating the complexity class.

If asked for a book report on "Of Mice and Men" , you wouldn't turn in "George shoots Lennie."

PLEASE take a bit of time to explain why you are claiming a particular runtime/space complexity class.

Bad:

sum = 0
for val in my_list:
  sum += val
return sum
# complexity analysis:
# runtime: O(n)
# space: O(1)

Okay:

sum = 0
for val in my_list:
  sum += val
return sum
# complexity analysis:
# runtime: O(n) (line 2 considers each element 'val' in list)
# space: O(1) (a single int `sum` is used to store the sum) 

( I will leave the Good example as an exercise to the reader).

Also, as an aside, complexity does not scale solely with the number of input examples. Anywhere you are caching lots of values, the space complexity probably increases with the cardinality of the data. You will have very different memory consumptions if you are caching 2^16 'a''s compared to caching the first 65,536 characters in the Unicode character set. Define the different components of the complexity class of your algorithm and refer to them when making statements about your algorithm's complexity.

thank u