how to do big-O analysis when 2 algorithms are involved

Question

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

1. sort the array using bubble sort ( n^2 )
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 ?

Answer 1

The way you did it, it would be O(n^2), since for large n, n^2 >>> logn

Answer 2

Only the higher order term. The complexity is always the complexity of the highest term.

Answer 3

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;-).

Answer 4

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.