chaoxu / algoprob

Algorithmic Problems and Exercises
7 stars 0 forks source link

Composition of running times #2

Open chaoxu opened 5 years ago

chaoxu commented 5 years ago

This is probably very difficult.

Note we might have two problems. A and B. Sometimes we want to express the running time of A and B. Let's say the running time of B with an input of size $n$ is $T(n)$.

So maybe there is an algorithm for A with running time $O(n T(n^2))$. One might be interested to express this. But this is not as useful if someone just wants to know the actual running time. One way is to actually write out the actual running time by hand.

That would be silly, but that's the best we can do right now.