<p>Like many things in life, there is no one definitive definition. For an algorithm to run in real-time, some people on the theoretical side say that this means it will take constant time per 'something.' Now you have to decide what a 'something' is but let me give a concrete example. Let's say that the input arrives one symbol at a time and you want to output the answer to a query as soon as a new symbol arrives. If calculating that output takes constant time per new symbol then you might say the algorithm runs in real-time.    An example of this is real-time exact string matching, which outputs whether a pattern matches the latest suffix of a text in constant time per new symbol. The text is assumed to arrive one symbol at a time.</p>

<p>However, an engineering answer will be less worried about "constant time" and more worried about it happening fast in practice and in particular fast enough that the result can be used by the time it is needed. So for example in robotics, if you want to play ping-pong it is useful for the robot to be able to work out where the ball is and move to hit it as the ball arrives, and not after the ball has passed. The asymptotic time complexity of the underlying algorithms will perhaps be of less interest there than just the observation that the code works out the location quickly enough.  To give another example, if you want to render video and can do it at 25 frames per second then it is reasonable to say that the rendering is happening in real-time.  </p>

<p>So basically you have two answers. One for the theoreticians/algorithmists and one that just says that you are doing the work as you need it on the fly.</p>

<p>EDIT: I should probably add that one extra feature one should require of even a constant time algorithm is that the time complexity is not amortised.  In this context, real-time == unamortised constant time. </p>

CC BY-SA 3.0
2011-07-15T15:51:18.383Z
2011-07-15T16:54:32.290Z
2011-07-15T16:54:32.290Z
Simd
<p>Maybe related to your question, you can look at <a href="http://en.wikipedia.org/wiki/Streaming_algorithm" rel="nofollow">streaming algorithms</a>. This model has some "real-time" flavor in some sense. </p>

<p>You can also look at results on real-time language recognition by <a href="http://en.wikipedia.org/wiki/Cellular-automaton" rel="nofollow">cellular automata</a>. For instance this <a href="http://www.sciencedirect.com/science/article/pii/S0022000072800047" rel="nofollow">paper</a>. There are <a href="http://scholar.google.com/scholar?q=real+time+cellular+automata" rel="nofollow">quite a lot of papers</a> on this subject.</p>

CC BY-SA 3.0
2011-07-15T20:36:12.617Z
2011-07-15T20:36:12.617Z
Bruno
<p>I have a feeling you're looking for a model that reflects the engineering meaning of "real time", but let me just point out there is something that theorists call real time (and is inspired by engineering "real time"). Look at this post by Lipton and the references there: <a href="http://rjlipton.wordpress.com/2011/01/12/stringology-the-real-string-theory/" rel="nofollow">http://rjlipton.wordpress.com/2011/01/12/stringology-the-real-string-theory/</a></p>

CC BY-SA 3.0
2011-09-26T15:46:51.450Z
2011-09-26T15:46:51.450Z
Sasho Nikolov
<p>Contrary to the various vague uses, I argue that:</p>

<p>Real-time computing in general is about the degree to which task time constraints are satisfied acceptably well with acceptable predictability according to application- and situation-specific acceptability criteria, given the current circumstances (overloads, failures, etc.). The general case of real-time is soft real-time. Hard real-time is a special case about always meeting all hard deadlines (not all deadlines are hard). Most systems that are real-time to any significant degree are soft.</p>

<p>I explain this in detail at <a href="http://real-time.org/_new/Print2HTML/Microsoft_PowerPoint_-_new_rt.org_draft_0.html" rel="nofollow">http://real-time.org/_new/Print2HTML/Microsoft_PowerPoint_-_new_rt.org_draft_0.html</a>.</p>

CC BY-SA 3.0
2011-09-25T22:23:25.890Z
2011-09-25T22:23:25.890Z
E. Douglas Jensen
<p>I would say "real-time" means you have contracts on the behavior of the machine over time; specifically with regards to how long a function will take to execute, and ordering guarantees when the system has a choice of multiple tasks to complete.</p>

CC BY-SA 3.0
2011-09-26T18:15:19.173Z
2011-09-26T18:15:19.173Z
Chad Brewbaker
<p>How is <a href="http://en.wikipedia.org/wiki/Real-time_computing" rel="nofollow">real-time computing</a> defined in theoretical computer science (e.g. complexity theory)? Are there complexity theoretic models designed to capture the real-time computation?</p>

CC BY-SA 3.0
2011-07-15T15:52:59.700Z
Are you looking for a formal definition? What do you hope to obtain from such a definition? Or are you more interesting in a computational model that takes into account time?
Dave Clarke
CC BY-SA 3.0
2011-07-15T20:06:03.627Z
Just like Raphael said, my experience is that "real time" is mostly an engineering term. I believe some definitions of "real time" computing amount to "A hard real-time problem is one for which the correctness of algorithms solving it depends on the amount of time taken to finish the computation," or something along those lines. Given this definition, I find Raphael's proposed formalization in terms of some kind of constant-time complexity metric pretty reasonable. In other words, what he said.
aegrisomnia
CC BY-SA 3.0
2011-07-18T19:27:33.713Z
Such models might also have been studied in descriptive complexity (which is strongly related to complexity of queries in databases).
Kaveh
CC BY-SA 3.0
2011-07-18T20:58:26.040Z
@Kaveh: How is query complexity related to real-time computing?
Dave Clarke
CC BY-SA 3.0
2011-07-19T01:35:41.947Z
@Dave, just a guess. Someone might have studied real-time database access.
Kaveh
CC BY-SA 3.0
2011-10-02T00:31:46.960Z
In the world of theoretical computer science that is not complexity theory, there is a model called the Timed Automaton.
Vijay D
<cc.complexity-theory><dc.distributed-comp>
How is Real-Time Computing defined?
ElArbi 
# How is Real-Time Computing defined?

(Asked by: username_0 on 2011-07-15)

How is [real-time computing](http://en.wikipedia.org/wiki/Real-time_computing) defined in theoretical computer science (e.g. complexity theory)? Are there complexity theoretic models designed to capture the real-time computation?

**Tags:** cc.complexity-theory, dc.distributed-comp

> **Comments:**
> **username_1**: Are you looking for a formal definition? What do you hope to obtain from such a definition? Or are you more interesting in a computational model that takes into account time?  
> **username_2**: Just like Raphael said, my experience is that "real time" is mostly an engineering term. I believe some definitions of "real time" computing amount to "A hard real-time problem is one for which the correctness of algorithms solving it depends on the amount of time taken to finish the computation," or something along those lines. Given this definition, I find Raphael's proposed formalization in terms of some kind of constant-time complexity metric pretty reasonable. In other words, what he said.  
> **username_3**: Such models might also have been studied in descriptive complexity (which is strongly related to complexity of queries in databases).  
> **username_1**: @username_3: How is query complexity related to real-time computing?  
> **username_3**: @Dave, just a guess. Someone might have studied real-time database access.  
> **username_4**: In the world of theoretical computer science that is not complexity theory, there is a model called the Timed Automaton.  

---

## 5 answers

### Answer by username_5 on 2011-07-15. Score: 11

Like many things in life, there is no one definitive definition. For an algorithm to run in real-time, some people on the theoretical side say that this means it will take constant time per 'something.' Now you have to decide what a 'something' is but let me give a concrete example. Let's say that the input arrives one symbol at a time and you want to output the answer to a query as soon as a new symbol arrives. If calculating that output takes constant time per new symbol then you might say the algorithm runs in real-time. An example of this is real-time exact string matching, which outputs whether a pattern matches the latest suffix of a text in constant time per new symbol. The text is assumed to arrive one symbol at a time.

However, an engineering answer will be less worried about "constant time" and more worried about it happening fast in practice and in particular fast enough that the result can be used by the time it is needed. So for example in robotics, if you want to play ping-pong it is useful for the robot to be able to work out where the ball is and move to hit it as the ball arrives, and not after the ball has passed. The asymptotic time complexity of the underlying algorithms will perhaps be of less interest there than just the observation that the code works out the location quickly enough. To give another example, if you want to render video and can do it at 25 frames per second then it is reasonable to say that the rendering is happening in real-time.

So basically you have two answers. One for the theoreticians/algorithmists and one that just says that you are doing the work as you need it on the fly.

EDIT: I should probably add that one extra feature one should require of even a constant time algorithm is that the time complexity is not amortised. In this context, real-time == unamortised constant time.


---

### Answer by username_6 on 2011-07-15. Score: 4

Maybe related to your question, you can look at [streaming algorithms](http://en.wikipedia.org/wiki/Streaming_algorithm). This model has some "real-time" flavor in some sense.

You can also look at results on real-time language recognition by [cellular automata](http://en.wikipedia.org/wiki/Cellular-automaton). For instance this [paper](http://www.sciencedirect.com/science/article/pii/S0022000072800047). There are [quite a lot of papers](http://scholar.google.com/scholar?q=real+time+cellular+automata) on this subject.


---

### Answer by username_7 on 2011-09-26. Score: 1

I have a feeling you're looking for a model that reflects the engineering meaning of "real time", but let me just point out there is something that theorists call real time (and is inspired by engineering "real time"). Look at this post by Lipton and the references there: <http://rjlipton.wordpress.com/2011/01/12/stringology-the-real-string-theory/>


---

### Answer by username_8 on 2011-09-25. Score: 1

Contrary to the various vague uses, I argue that:

Real-time computing in general is about the degree to which task time constraints are satisfied acceptably well with acceptable predictability according to application- and situation-specific acceptability criteria, given the current circumstances (overloads, failures, etc.). The general case of real-time is soft real-time. Hard real-time is a special case about always meeting all hard deadlines (not all deadlines are hard). Most systems that are real-time to any significant degree are soft.

I explain this in detail at <http://real-time.org/_new/Print2HTML/Microsoft_PowerPoint_-_new_rt.org_draft_0.html>.


---

### Answer by username_9 on 2011-09-26. Score: 1

I would say "real-time" means you have contracts on the behavior of the machine over time; specifically with regards to how long a function will take to execute, and ordering guarantees when the system has a choice of multiple tasks to complete.


---

