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