Are there any machine learning algorithms or algorithms categories which have predictable execution times (guaranteed minimal/maximal execution time e.g. when the algorithm is run on a single processor which is not loaded with other processing tasks) for predictions given any possible input making them suitable for the use in hard real time systems?
making them suitable for the use in hard real time systems
Not sure what you mean by "hard" real time systems, but what you describe is basically the context of data streams. That is a whole branch with its own algorithms. Since you don't specify much, I leave the answer here, pointing out what kind of algorithms you should research.
Hope this helps!