2
votes
1answer
178 views

How this Fibonacci exponentiation by squaring algorithm works?

This is one of the best algorithms to calculate the nth Fibonacci sequence. it needs O(log(n)) time to do its job, so it's so efficient. I found it somewhere but don't know how it works! Can anyone ...
-4
votes
1answer
719 views

What is the big-O cpu time of Euclid's Algorithm of “Greatest common divisor of two numbers”

Looking at Euclid's algorithm for the "Greatest common divisor of two numbers", I'm trying to divine the big-O cpu time for numbers K, and N. Can anybody help? This is the algorithm as I understand ...
0
votes
1answer
53 views

clarification about amortized analysis

I was going through an article here In the section named Aggregate Method ,the author says Then summing over the entire sequence, all the 1's sum to O(n), and all the di also sum to O(n). That ...
0
votes
1answer
174 views

Help with algorithmic complexity in custom merge sort implementation

I've got an implementation of the merge sort in C++ using a custom doubly linked list. I'm coming up with a big O complexity of n^2, based on the merge_sort() > slice operation. But, from what I've ...
10
votes
7answers
2k views

Big Oh notation does not mention constant value

I am a programmer and have just started reading Algorithms. I am not completely convinced with the notations namely Bog Oh, Big Omega and Big Theta. The reason is by definition of Big Oh, it states ...