# Big O notation for multiple functions

I've a question regarding big O notation when one is using multiple functions. Lets say I want to find out what the time complexity is for the following pseudo code:

``````heap sort array of size n
for i = 1 to n{
retrieve array[i]
change value of array[i]
}
``````

I know that using heap sort is O(n log(n)). Since retrieving and changing data in an array is O(1), the loop is of complexity O(n). Now my question is: what is the complexity of this code as a whole? Is it just the largest time complexity; O(n log(n)) in this case? If so, what would be the complexity of a function that would look like this:

``````for i = 1 to n{
// nothing fancy here
}
for y = 1 to n{
// nothing fancy here either
}
``````

-
Homework? Sounds like it. – EmeryBerger Feb 8 '11 at 14:42
The first example is homework. But fact is that I 'figured' out the rest of the time complexity things myself. The second example however is not homework. Only thing I want to know is the theory, so you can also only answer the 2nd example - which wouldn't be my homework. – EthanM Feb 8 '11 at 14:54
"Since retrieving and changing data in an array is O(1)": when assessing the complexity of comparison sorts, one traditionally counts (and provides big-O asymptotics for) the number of comparisons needed to sort an array of size n, not the time the algorithm takes (think about the case where your array is on a tape, and you have to rewind the tape to access elements). Technically you are right, but your formulation of the question shows that you did not fully grasp what complexity theory is about. There is no "complexity as a whole": you have to specify what you are counting exactly. – Alexandre C. Feb 8 '11 at 15:07

Big-O notation is about which factor dominates as `n` (input size) approaches infinity. So if you have two chunks of code `A` and `B` executed sequentially, then the overall time behavior would be the larger of O(`A`) and O(`B`).

In your case, if the heapsort is an `O(nlogn)` algorithm, and the loop is simply an `O(n)` algorithm, then as `n` approaches infinity the `nlogn` will eventually be way bigger, so it is the only term that matters. So your overall time behavior is `O(nlogn)`.

Of course this is all theory. In the real world, if you were to be doing something slow inside that loop (like I/O), then your `n` might have to get huge (perhaps bigger than it could ever reasonably get) before the mergesort is slower than the loop.

-
Thanks you very much. That cleared it up! – EthanM Feb 8 '11 at 15:00
``````for i = 1 to n{
// nothing fancy here
}  //O(n)

for y = 1 to n{
// nothing fancy here
}  //O(n)
``````

So together it is `O(n) + O(n) = O(n)`.

-
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}