File: quicksort_runtime.coffee

package info (click to toggle)
coffeescript 1.10.0~dfsg-1
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 3,292 kB
  • sloc: makefile: 62
file content (13 lines) | stat: -rw-r--r-- 327 bytes parent folder | download | duplicates (4) 
1
2
3
4
5
6
7
8
9
10
11
12
13
 
# Beautiful Code, Chapter 3.
# Produces the expected runtime of Quicksort, for every integer from 1 to N.

runtime = (N) ->
  [sum, t] = [0, 0]
  for n in [1..N]
    sum += 2 * t
    t = n - 1 + sum / n
  t

console.log runtime(3) is 2.6666666666666665
console.log runtime(5) is 7.4
console.log runtime(8) is 16.92142857142857