CODEWITHSUNDEEP
algorithmbinary-searchfibonacci
Mayesh Mohapatra
Mayesh Mohapatra

Reputation: 42

Time Complexity Of Fibonacci Search compared with Binary Search

Why is it that the average time complexity of fibonacci search is same as that of binary search's time complexity inspite of more comparisons being executed by fibonacci search in comparison to binary search

Upvotes: 1

Views: 404

Answers (1)

Mr R
Mr R

Reputation: 794

Time complexity is about how things scale with increasing input size, not about the cost of each iteration.

So O(log n) - which they both are - is saying that if you doubled the length of the input the effort involved is about 30% more than for the original input. The cost of doing it is not indicated - just that given a cost X for a length N, doubling the length (2N) results in ~30% more cost.

To compare the performance of two searches - the time complexity helps with understanding how things scale - so a O(log N) is better than O(N) - but the size of N and the cost of an operation are just as important in making the decision.. For instance for very small size and fast comparison an O(N) algorithm might be faster than an O(log N) algorithm, however as the N grows the performance balance is likely to change to the other way.

Great answer to previous question on time complexity https://stackoverflow.com/a/2307314.

Upvotes: 2

Related Questions