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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Are $p$ and $q$ functions or constants? $\endgroup$
    – Badr B
    Commented Jan 5, 2020 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$
    – ramseysdream111
    Commented Jan 5, 2020 at 14:11
  • $\begingroup$ @BadrB I guess p and q are functions,but it really didn't say anything than this. $\endgroup$
    – Mostafa Mohamed
    Commented Jan 5, 2020 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
    Commented Jan 6, 2020 at 13:06

1 Answer 1

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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