Monthly Archives: November 2012

Merge Sort program in C

It is rather amazing, that many programmers are unable to write ‘Merge Sort’ correctly. With its guarantee of O(n log n) time complexity, it is a dependable sorting algorithm. Also it can be used to count number of inversions in an array … Continue reading

Posted in Programming | Tagged , , | 27 Comments

Fastest way to compute Fibonacci Number

While we all know that matrix exponentiation is asymptotically fastest way to compute NthFibonacci number, there is a still faster way- If we know F(k) and F(k+1), then we can find F(2k) = F(k)[2F(k+1) – F(k)] F(2k+1) = F(k+1)2 + F(k)2 This is fast doubling. Here … Continue reading

Posted in Programming | Tagged | 8 Comments