Suppose we have a human-written program that's N-bits long. It takes an input, and generates an infinite output by performing some hashing of the input. We run it on an M-bit input to get some output, then stop it manually.
Now suppose we have an input and the output made by this program. But we don't have the program. Suppose we want to discover by brute force what the program was.
The brute-force algorithm will create every possible program up to N bits long, and run each one until either a difference in outputs is found, or it found the correct output, or too much time has passed.
How do you come up with the order-notation for this brute-force algorithm?
Now suppose we have an input and the output made by this program. But we don't have the program. Suppose we want to discover by brute force what the program was.
The brute-force algorithm will create every possible program up to N bits long, and run each one until either a difference in outputs is found, or it found the correct output, or too much time has passed.
How do you come up with the order-notation for this brute-force algorithm?