I'm trying to figure out the time complexity of a program that reads N lines but has a 1% chance of starting over at the end. I'm also curious about how this would change if there was a chance to restart after each line instead. Can anyone help clarify this?
3 Answers
You can think about both worst-case and amortized time in this case. For worst-case analysis, you'd say it's basically O(∞)—it's unbounded. But for amortized time, the first case would be Θ(N) since you just read all lines, and if after each line it might restart, then it could get pretty messy and even lead to exponential time complexity instead.
Good point! Any chance of restarting matters for the worst case. It doesn't really matter if it's a tiny chance like 1% or a huge one—if there's always a chance for a restart, it complicates things. If there's no clear correlation between N and the likelihood of restarting, then you run into a situation without a clear time complexity, which seems chaotic! If restarting is always a possibility, we could say it’s O(∞), but again, it’s hard to express that as a proper function of N.
The situation is a bit tricky! Since 'a line' isn't a solid measure of size—because each line can have a different amount of data—it's hard to pin down. Even if we consider reading one line as an O(1) task, we can't really predict how many lines will be read in total, so it's not really well-defined.
What if there's a chance to stay on the same line? I know it could also be unbounded or infinite, but how does that affect the amortized time, which I'm still not sure about?