(I am of course just making that equation up, but I assume it would look something like that).
-
-
Show this threadThanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
max(t_i) * (n-1) + sum(t_i) is a lower bound and tight in case max(t_i) = t_0. Upper bound is sum(t_i)*n which is tight in case there's only one stage. Neither *has* to be tight though. Don't think a general formula exists.
-
Where are you getting those bounds from, though? Why would it matter if max(t_i) is on t_0 or anywhere else?
- Show replies
New conversation -
-
-
Pretty sure you are exactly right - this would make a great awful interview question. Proof sketch: consider the distance between two adjacent items over time. Distance starts out as zero, easy to see max is exactly t_worst.
-
When an item finishes, the next item will be exactly t_max behind it - since after the biggest task, the gap between any two items is exactly t_max.
End of conversation
New conversation -
-
-
Took me a while to reach the same conclusions... There are a couple of assumptions though: each stage can only process one item at a time; an item enters a stage as soon as possible, meaning that all items must be ready to be processed before the pipeline starts.
- Show replies
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.