2
$\begingroup$

I am struggling to grasp fully grasp complexity reductions, I have this example that I am working through and can not fully comprehend how to determine the complexity of one algorithm given the complexity of another, either $ O$ or $\Omega$

The example algorithm is:

  Input: left: array of n integers
  Input: right: array of m integers
  Input: n,m:  size of left and right
  Output: TwoSumSplit(left, right,t)
1 mix = Array()
2 for i = 1 to n do:
3  Add 3(left[I]) + 1 to mix
4 end
5 for i = 1 to m do:
6  Add 3(right[I]) + 1 to mix
7 end
8 return TwoSum(mix,3t)

the complexity of TwoSumSplit(TSS) is $\Theta(n + m + TS(n + m))$

My question is how can I determine the complexity of an algorithm given the complexity of another, for example:
$if\space TS(n) = O(n)$
$if\space TS(n^2) = O(n^2)$

then what can be determined of the complexity of TSS?

Using the notation of $A \le_p B$,I know that "TSS surrounds TS", along with rules such as reducing from unknown to known for $O$ and reducing from known to known for $\Omega$. I've determined that from statements like $if\space TS(n) = \Omega(n)$ nothing can be determined using these stated rules/observations.

Source: Dr. Hendrix; Analysis of Algorithms. Spring 2017 USF

$\endgroup$
3
$\begingroup$

If $TS(n) = O(n)$ then $TSS(n,m) = \Theta(n+m)$.

If $TS(n) = O(n^2)$, then all we can say is that $TSS(n,m) = \Omega(n+m)$ and $TSS(n,m) = O(n^2+m^2)$.

How did I reach these conclusions? First of all, clearly $TSS(n,m) = \Omega(n+m)$. If $TS(n) = O(n)$ then $TS(n+m) = O(n+m)$ and so $TSS(n,m) = O(n+m + O(n+m)) = O(n+m)$. Altogether, $TSS(n,m) = \Theta(n+m)$.

If $TS(n) = O(n^2)$ then $TS(n+m) = O((n+m)^2) = O(n^2+m^2)$, since $(n+m)^2 = \Theta(\max(n,m)^2) = \Theta(n^2+m^2)$ (you might prefer the middle form to the one on the right). Therefore $TSS(n+m) = O(n+m+O(n^2+m^2)) = O(n^2+m^2)$.

$\endgroup$
  • $\begingroup$ +1 thank you for clarifying this to me. $\endgroup$ – moose0306 Apr 30 '18 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.