Question about runtime

If I have a for loop that runs in linear runtime inside which I have a while loop that keeps generating a number until the requirements are met, what runtime would I have?

This is a surprisingly tricky question, that depends on a lot of circumstances, specifically what a number, the requirements and generate means.

More precisely, each of these operations has its own runtime. There are methods for generating a random natural number, but they all take worst-case infinite time. Luckily, on a computer, we are not dealing with actually possibly arbitrary-sized natural numbers, since int and all other integer types have a size limit.

Now, even for those numbers, you can come up with algorithms that might loop forever.

Furthermore, checking that “requrements are met” also takes time, and this also needs to be taken into account.

If you “generate” numbers by looping from 1 to 5 and checking your condition takes constant time, then your loop will only take constantly many steps and also run in constant time.

If you loop forever until some condition is met, “randomly” generating a number each time, then your loop will terminate with probability 1*, while still having unbounded run-time in the worst case since you might take a long time until you reach the correct number.

So, to conclude, you need to be a bit more specific if you want a concrete answer.

*: Probabilities are weird. More about this in Maths for Computer Scientists 3 (aka Mathe für Informatiker*innen 3)

Loop like so: for int i = 0; i < some_constant; i++ => O(c) = constant runtime
While loop for search of length n or something without a constant limit for the while loop (while(i < 26):slight_smile: has runtime O(n).

Any simple integer operations, like generate a number (do you mean counting num up/down?) is O(1).

If you have a for loop with O(n) and your while-loop duration is not dependent on a constant but on arbirary length, you got yourself a nested loop with O(n), which normally sets it to n^2.

So either your for loop or your while loop have to be upgraded to O(c), to at least have O(n*c) = O(n) = linear. I hope I got this one right, please immediately correct me if I didn’t.

1 Like

I was a bit confused but I figured a way to make my while loop in constant runtime.

So I’ll have a for loop with linear runtime inside which I’ll have a while loop with constant runtime.

That should still be a linear runtime and follow the guidelines of the project right?

If you have something like this:

for(int i = 0; i < constant; i++){
  for(int j = 0; j < length(input); j++){
   <do something in constant time>

Then your program has constant\cdot \mathcal{O}(length(input)) = \mathcal{O}(length(input)) runtime, which is indeed linear.