$\begingroup$
$\endgroup$
4
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?
xskxzr
7,6235 gold badges24 silver badges48 bronze badges
asked Jan 3, 2020 at 17:28
-
$\begingroup$ Are $p$ and $q$ functions or constants? $\endgroup$Badr B– Badr B2020年01月05日 13:06:14 +00:00Commented 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– ramseysdream1112020年01月05日 14:11:01 +00:00Commented 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– Mostafa Mohamed2020年01月05日 14:31:17 +00:00Commented 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– shgr10922020年01月06日 13:06:30 +00:00Commented Jan 6, 2020 at 13:06
1 Answer 1
$\begingroup$
$\endgroup$
The total running time of $A_3$ will be bounded by $p(x)+q(y)$ where $x$ is the size of the input to $A_1 $and $y$ is the size of the output of $A1$. Now time complexity is usually written in terms of the size of the input of the algorithm and nothing else, so if $y=f(x)$ then the running time of $A_3$ will be $\mathcal{O}(p(x)+q(f(x)))$
answered Jan 6, 2020 at 8:44