Simple recursive algorithm and its cost.

main.go

package main

import "fmt"

var cost int

func f2(s, e int) int {
	cost += 1

	if e <= s {
		return 1
	}

	mid := s + ((e - s) / 2)
	return f2(s, mid) + f2(mid+1, e)
}

func main() {
	for i := 1; i < 1000; i++ {
		cost = 0
		f2(0, i)
		fmt.Printf("%d\t%d\t\n", i, cost)
	}
}