;; Exponential time, small-o of (sqrt(2))^n

(define (fibs n)
  (cond ((= n 0) 1)
	((= n 1) 1)
	(else (+ (fibs (- n 1))
	         (fibs (- n 2))))))

;; Linear time, big-Theta of n

(define (fast-fibs n)
  (define (fast-fibs-helper end cur cur-term next-term)
    (if (= cur end) cur-term
	(fast-fibs-helper
	    end (+ cur 1) next-term (+ next-term cur-term))))
  (fast-fibs-helper n 0 1 1))