# How to get Algorithm complexty based on another 2 algorithms?

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?

• Are $p$ and $q$ functions or constants? – Badr B Jan 5 at 13:06
• @MostafaMohamed I guess it depends on what the size output of the first algorithm is as a function of the size of its input? – pkwssis Jan 5 at 14:11
• @BadrB I guess p and q are functions,but it really didn't say anything than this. – Mostafa Mohamed Jan 5 at 14:31
• 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. – shgr1092 Jan 6 at 13:06

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)))$$