We suggest different code solutions to the task of counting the number of pythagorean triples (https://en.wikipedia.org/wiki/Pythagorean_triple) with a given sum p.
We begin with the most naive solution, and gradually move to more efficient ones.
When computing code complexity, we
a. define the entire content of the innermost loop as an “atomic operation” which takes constant time.
b. describe the complexity as a function of p (i.e., use p as the “problem size”). the formal definition of “problem size” is the size it takes to represent the input, i.e. n = log(p). working with p here is easier and more intuitive, but we’ll mention also the complexity as a function of n.
v_0: go over all triplets of numbers in the relevant range. note that we need to make sure that a<=b, otherwise we’ll be counting each solution twice. Complexity: O(p**3) = O(8**n).
v_1: very similar to v_0, but with simplified conditions (we realize it can’t be the case that a==b, and that b