how to do big-O analysis when 2 algorithms are involved
I'm confused about how to do big-O analysis for the following problem -
find an element from an array of integers. ( an example problem)
my solution
- sort the array using bubble sort ( n^2开发者_开发技巧 )
- binary search on the array for a given element (logn)
now the big-O for this is n^2 or n^2 + logn ? Should we only consider the higher term ?
Big-O for a problem is that of the best algorithm that exists for a problem. That for an algorithm made of two steps (like yours) is indeed the highest of the two, because e.g.
O(n^2) == O(n^2 + log n)
However, you can't say that O(n^2)
is the correct O
for your sample problem without proving that no better algorithm exists (which is of course not the case in the example;-).
Only the higher order term. The complexity is always the complexity of the highest term.
The way you did it, it would be O(n^2), since for large n, n^2 >>> logn
To put the analysis, well, more-practically (if you prefer, crudely) than Alex did, the added log n doesn't have an appreciable effect on the outcome. Consider analyzing this in a real-world system with one million inputs, each of which takes one millisecond to sort, and one millisecond to search (it's a highly-hypothetical example). Given O(n^2), the sort takes over thirty years. The search takes an additional 0.014 seconds. Which part do you care about improving? :)
Now, you'll see algorithms which clock in at O(n^2 x logn). The effect of multiplying n^2 by log n makes log n significant - in our example, it sees our thirty years and raises us four centuries.
精彩评论