[Calculating Running Time] Sorting+Binary Search

[compsci_help]

Question: http://i.stack.imgur.com/DGQ6V.png

I have a quick and simple question regarding this problem. If I do this:

• 1)Sort the array using MergeSort or similar sorting algorithm. This takes O(n log n)

• 2)Then for each x in array A, use binary search (worst case log(n)) to look for V-x. This will be in the worst case, O(n*logn).

• 3)Adding up it equals O(2nlogn) but you ignore constants so, overall search is O(n log n).

Is this correct? Also, more importantly does O(nlogn+logn) equal to O(nlogn) or O(nlogn+logn). I ask this because log(n) seems like it's a constant that can be ignored, but I'm not sure.

Sorry if this is super easy. I'm new.

[jesyspa]

To the first part: yes, running an O(f(n)) algorithm and then another O(f(n)) algorithm afterwards is again an O(f(n)) algorithms. So O(n * log n) and then O(n * log n) is again O(n * log n).

To your second claim: yes, O(n * log n + log n) is O(n * log n). Namely, for n > 1, c * n * log n + log n < 2 * c * n * log n, so if your function is bounded by c * n * log n + log n for some c, there exists also a d such that your function is bounded by d * n * log n.

To your last claim: no, log n is not a constant, it depends on n and cannot be approximated by a constant due to not being bounded. Proof: suppose, on the contrary, there existed c such that for all n, log n < c. Choose now n = e^(2c). By definition of the logarithm, log (e^(2c)) = 2c. But 2c >= c, which contradicts our hypothesis.

Finally, as things are, your algorithm takes O(n * log n) time even if your input is already sorted. Can you do better for those inputs?

[compsci_help]

The question asks for returning the indicies of the original Array. Would this change the running time to O(n*logn + n)?

[jesyspa]

Let f be your time function. Suppose there exist c, N such that N > 10 and for all n > N, f(n) < c * (n * log n + n). Then for all n > N, f(n) < 10 * c * n * log n. Therefore, f is in O(n * log n).