see Computing Parity of Combinatorial Functions, S. Cha. CSIS Technical Reports, Feb 2011, n 281

- | Computational Complexities | |
---|---|---|

Acutal value | Parity | |

factorial n! | Θ(n) |
O(1) |

Fibonacii F_{n} | Θ(n) |
O(1) |

Lucas L_{n} | Θ(n) |
O(1) |

Power n^{k} | Θ(logk) |
O(1) |

Permute P(n, k) | Θ(n-k) |
O(1) |

Binomial Coefficient C(n, k) | Θ(min(n-k,k)) |
O(log(n)loglog(n)) |

Σ_{i =1~ n}i^{k} | Θ(n) |
O(1) |