0
$\begingroup$

I had quiz last week and it says: suppose algorithms $A_1$ and $A_2$ have worst-case time bound $p$ and $q$, respectively. Suppose algorithm $A_3$ consists of applying $A_2$ to the output of $A_1$. (The input for $A_3$ is the input for $A_1$.) Give a worst-case time bound for $A_3$.

How could I calculate the worst case based on the given info?

$\endgroup$
  • $\begingroup$ Are $p$ and $q$ functions or constants? $\endgroup$ – Badr B Jan 5 at 13:06
  • $\begingroup$ @MostafaMohamed I guess it depends on what the size output of the first algorithm is as a function of the size of its input? $\endgroup$ – pkwssis Jan 5 at 14:11
  • $\begingroup$ @BadrB I guess p and q are functions,but it really didn't say anything than this. $\endgroup$ – Mostafa Mohamed Jan 5 at 14:31
  • $\begingroup$ I wonder if the quiz assumed that the size of the output of the first algorithm was only 1... I certainly did when I looked at the question without any other details. So, if p+q was an answer, that would probably have been correct. $\endgroup$ – shgr1092 Jan 6 at 13:06
1
$\begingroup$

The total running time of $𝐴_3$ will be bounded by $𝑝(𝑥)+𝑞(𝑦)$ where $𝑥$ is the size of the input to $𝐴_1 $and $𝑦$ is the size of the output of $𝐴1$. Now time complexity is usually written in terms of the size of the input of the algorithm and nothing else, so if $𝑦=𝑓(𝑥)$ then the running time of $𝐴_3$ will be $\mathcal{O}(p(x)+q(f(x)))$

$\endgroup$

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.