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

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.