asymptotic time complexity of scheme functions

Question

I am trying to teach myself scheme and the concept I am struggling with the most is space and time complexity. I was doing some of the exercises at the end of the chapter and I have not been able to figure out the following two. I am trying to figure out an asymptotic time complexity (tight bound) for each of the functions.

;; Finds the largest number below 1000000000 which is divisible by both 3 and 5.

(define (largest-div-3-or-5)
  (define (div-3-and-5? n)
    (and (= (remainder n 3) 0) (= (remainder n 5) 0)))
  (define (iter n r)
    (cond ((= n 1000000000) r)
          ((div-3-and-5? n) (iter (+ n 1) n))
          (else (iter (+ n 1) r))))
  (iter 1 0))

For this I thought the asymptotic time complexity was O(n) because we are calling the iterative function once everytime unless the stop condition is satisfied.

The second function is given by:

(define (sum-of-cubes-2-different-ways max-n)
  (define (cube n) (* n n n))
  (define (iter n1 n2 n3 n4 results)
    (cond ((> n1 max-n) results)
          ((> n2 max-n) (iter (+ n1 1) 1 1 1 results))
          ((> n3 max-n) (iter n1 (+ n2 1) 1 1 results))
          ((> n4 max-n) (iter n1 n2 (+ n3 1) 1 results))
          ; make sure n1,n2 are distinct from n3,n4:
          ((or (= n1 n3) (= n1 n4) (= n2 n3) (= n2 n4)) 
           (iter n1 n2 n3 (+ n4 1) results))
          ((= (+ (cube n1) (cube n2)) (+ (cube n3) (cube n4)))
           (iter n1 n2 n3 (+ n4 1) (cons (list n1 n2 n3 n4) results)))
          (else (iter n1 n2 n3 (+ n4 1) results))))
  (iter 1 1 1 1 (list)))

This seemed to me that it was O(n^2). It is difficult to explain why I think so I am just eyeballing it really.

Answer 1

The first one's time complexity is O(n), because you are performing a constant number of operations per element in the list.

The second one's time complexity is O(n^4). You are iterating over every possible combination of 4 integers picked from the range [0,n). There are n choices for the first number, n choices for the second number, n choices for the third number, and n choices for the fourth number. Therefore, there are n^4 possible combinations of the four numbers, and you perform a constant number of operations per combination, which means that the overall complexity is O(n^4).