Order(N) Demo

#! /bin/bash

doSumAll () {

    local AWK='
{ for (j = 1; j <= $1; j++) sum += j; }
END { printf ("doSumAll %s is %s\n", $1, sum); }
'
    echo "${1}" | awk -f <( printf '%s' "${AWK}" ) > /dev/null
}

doFibonacci () {

    local AWK='
BEGIN { a = 0; b = 1; }
{ for (j = 2; j <= $1; j++) { c = a + b; a = b; b = c; } }
END { printf ("doFibonacci %s is %s\n", $1, b); }
'
    echo "${1}" | awk -f <( printf '%s' "${AWK}" ) > /dev/null
}

doEvenOdd () {

    local AWK='
{ for (j = 1; j <= $1; j++) a = j % 2; }
END { printf ("doEvenOdd %s is %s\n", $1, --j % 2); }
'
    echo "${1}" | awk -f <( printf '%s' "${AWK}" ) > /dev/null
}

Real () { r="${1}"; r="${r#*real}"; r="${r%%user*}"; echo ${r}; }

Compare () {

    local N="${1}"

    TimeA="$( ( time doSumAll "${N}" ) 2>&1 )"
    TimeB="$( ( time doFibonacci "${N}" ) 2>&1 )"
    TimeC="$( ( time doEvenOdd "${N}" ) 2>&1 )"

    printf 'TimeA %s %s\n' "${N}" "$( Real "${TimeA}" )"
    printf 'TimeB %s %s\n' "${N}" "$( Real "${TimeB}" )"
    printf 'TimeC %s %s\n' "${N}" "$( Real "${TimeC}" )"
    echo
}

    for n in {1..6}000000; do
        Compare "${n}"
    done