<p>If 'C' isn't constant in your real-world application, then the abstract model you're apply isn't meaningful anymore.  The abstraction isn't broken; you're just using the wrong one.  </p>

<p>The thing about abstractions is that you can make them as precise or as vague as you need them to be for your application. You could say "This algorithm has time complexity of at least 0 and at most never terminates."  It would be correct, but it's so abstract that it's completely useless. If C is growing with 'n' rather than being constant, then the algorithm you're analyzing is now a new algorithm. Figure out how C is growing in relation to N, drop it into your expression and do the algebra.  Voila; your expression is now more meaningful. </p>

<p>You can analyze an algorithm all day long, but if it doesn't represent what's actually happening, then you're not doing yourself any good.  There isn't any special name for this: it's just a matter of garbage-in; garbage-out.  </p>

CC BY-SA 3.0
2011-04-20T04:24:06.737Z
How does this answer the question? The person asking the question is aware of the abstractions or in this case idealistic computation model problem. He is asking for realistic models which are under research or practice.
Sai Venkat
CC BY-SA 3.0
2011-04-20T04:29:05.750Z
That is actually quite helpful, Joe. But I don't believe it is just a matter of giving up. The comments on here are helping me clarify that what I am asking for is more information on exactly these other abstractions. Also, your example is a little odd, because big-O time complexity is never given as a range, for deterministic algorithms, in my experience. [Sai - exactly, thanks!]
Ian
CC BY-SA 3.0
2011-04-20T17:09:40.240Z
@Ian You might want a different Bachmann–Landau notation for that, then. 'Big-Omega' for the lower-bound or 'Big-Theta' for a function bounded both above and below.
Joe
CC BY-SA 3.0
2011-04-20T17:19:21.907Z
@Ian your answer is quite useful, however. Thank you =)
Joe
CC BY-SA 3.0
2011-04-20T04:11:54.377Z
2011-04-20T04:11:54.377Z
Joe
<p><strong>What Big-O Means</strong></p>

<p>Big-O notation, or <a href="http://mathworld.wolfram.com/LandauSymbols.html" rel="nofollow">Landau Symbols</a>, are not particular to any model of computation, or even to computer science. When used to illustrate the asymptotic complexity of an algorithm, they are always given relative to some model of an abstract machine, even if that abstraction isn't made explicit.</p>

<p>In texts on algorithms the model used is often a <a href="http://en.wikipedia.org/wiki/Random_access_machine" rel="nofollow">RAM machine</a>, and usually is used without explicit acknowledgement (see for example the unqualified use of big-O notation on the wikipedia pages for <a href="http://en.wikipedia.org/wiki/Quicksort" rel="nofollow">Quicksort</a> or <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="nofollow">Dijkstra's Algorithm</a>, or the examples in the <a href="http://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities" rel="nofollow">Table of Common Time Complexities</a>).</p>

<p>On a different machine model, or on a real machine, the scaling properties will be different. With a suitable model of computation, one could derive the asymptotic performance and state it in big-O notation, and the result may be different to that for the RAM machine and therefore to commonly published big-O values. </p>

<p>For example: on a machine with sequential memory (a Turing Machine with a single tape, say), binary search no longer has a running time O(log n) - the commonly cited result for a RAM machine - because traversing the tape requires O(n) time. </p>

<p>As a second example, <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.2225&amp;rep=rep1&amp;type=pdf" rel="nofollow">this chapter</a> shows an explicit computational model described, and used to derive the asymptotic performance of various algorithms.</p>

<p><strong>Realistic Performance Envelopes</strong></p>

<p>Analysing the asymptotic complexity of an algorithm makes the assumption that the algorithm would still be viable regardless of the problem size. But ultimately, no real machine can cope with infinite size problems. So unless the algorithm is O(1) in time and space, there will always come a point beyond which the performance of the algorithm is limited by the capacity of the machine, rather than the theoretical complexity bound. </p>

<p>It would be perfectly possible to analyse the algorithm (using a realistic model of a resource-limited machine) to determine the maximum solvable problem size. And if the real machine went through different modes of computation at different problem sizes (for example, it stops being able to hold data in cache at a particular size, then stops being able to hold it in RAM, then runs out of disk space, etc), one could work out where these transitions would occur, and give a more detailed characterization of its performance envelope. These kinds of analysis might be important if you need to make guarantees about real-world performance, but are completely unrelated to asymptotic performance analysis.</p>

<p>There isn't a special big-O like notation for those results, you would just give the equations for the performance explicitly. Given that you are now dealing with explicit upper bounds, big-O notation would be inappropriate.</p>

CC BY-SA 3.0
2011-04-20T15:43:51.017Z
I've brought citations and insights from your comments into this answer, as a summary - please let me know if I've got the wrong end of the stick anywhere. I appreciate your help, but I want to make sure that the question has a useful answer, because I know stack exchange often come up high on google searches.
Ian
CC BY-SA 3.0
2011-04-20T15:57:39.137Z
I don't understand why you use "big-0 is not useful" when you cross machine model boundaries. What breaks down is the particular abstraction you're using. Big-Oh is NOTATION, not truth.
Suresh Venkat
CC BY-SA 3.0
2011-04-20T17:14:55.183Z
I didn't use it at that point. I used it at the point that I talked about a real machine with a finite capability. But I take your point.
Ian
CC BY-SA 3.0
2011-04-20T19:13:47.350Z
I feel this discussion is getting rapidly out of scope, but I'm not even sure why you'd say 'asymptotic complexity is not useful'. That is again a concept - a way of describing complexity. The failure here is a failure of the model to adjust to real-life scaling.
Suresh Venkat
CC BY-SA 3.0
2011-04-20T22:39:55.620Z
@Suresh - I don't mind getting out of scope - I learn a lot about my poor concept-space from bumping up against these objections to my vague language. Maybe it isn't helpful for others, but it is always helpful to me! ... That said, surely asymptotic measures of anything cease to be useful at the point where there is a real hard limit. For any real computer, there will be a limit to the problem size. That's all I mean. If there's a better way to phrase it, I'm happy to edit. For now I'll just remove that sentence. Thanks again.
Ian
CC BY-SA 3.0
2011-04-21T04:37:21.977Z
To be pedantic, **binary search cannot be O(log n)**, for the trivial reason that binary search is not a function from the integers to the integers.  The *running time* of binary search is O(log n) in the standard RAM model and is O(n) in the single-tape Turing machine model.
Jeffε
CC BY-SA 3.0
2011-04-22T19:36:08.047Z
Of course asymptotics are only approximations for finite realities. But that is what we do in (T)CS: Finding abstract models you can work with for awefully intricate real problems/machines.
Raphael
CC BY-SA 3.0
2011-04-20T15:42:03.873Z
2011-04-21T12:55:34.367Z
2011-04-21T12:55:34.367Z
Ian
<p>While I'm not entirely sure what you're getting at, there are a number of frameworks that explicitly capture the cost changes that show up when we hit real resource limits. Three examples: </p>

<ol>
<li>the external memory framework that emphasizes the expense of going to disk (idealized by setting main memory reference costs to 0, and disk reference costs to some fixed constant)</li>
<li>The cache-oblivious model that assumes an unknown cache size and performance hits for going beyond.</li>
<li>The streaming computational model in which only you're only allowed sublinear working storage. </li>
</ol>

<p>Are these along the lines that you're thinking ? </p>

CC BY-SA 3.0
2011-04-19T22:57:02.073Z
So this is just a general difference between a theoretical time complexity of the algorithm, and the time complexity of a practical implementation on a more realistic model of an abstract machine? If the former then is big-O notation, does the latter have a name? I've got a shelf full of books that talk about the big-O of various algorithms, and I'm used to calculating the same. Is the more realistic model actually done?
Ian
CC BY-SA 3.0
2011-04-20T00:08:16.447Z
I think you have to separate two things. It is the notion of cost that changes when one moves to these models. The rules for how to charge an operation are different, in other words. The big-Oh notation is still used here to describe asymptotic complexity bounds
Suresh Venkat
CC BY-SA 3.0
2011-04-20T04:24:00.637Z
Grrr. I'm feeling dumb now.  I've never seen a big-O given with a description of the abstract machine. Are you saying that for a different machine you'd have a different asymptotic complexity (in which case, this seems odd, because in any finite memory machine, the asymptotic time would be infinite - eventually it would always run out of memory), or are you saying that the big-O is irrelevant, because the algorithm needs to be fed through a more realistic model of the computer to find some actual expected performance (in which case, that's exactly what I'd love to learn more about).
Ian
CC BY-SA 3.0
2011-04-20T04:38:57.263Z
Big O does come with description of abstract machine, probably RAM model. But if you want to understand how the effects of realistic model affects the Big-O you may want to refer some paper on such model like Cache Oblivious http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.2225&rep=rep1&type=pdf
Sai Venkat
CC BY-SA 3.0
2011-04-20T06:11:49.363Z
Consider the external memory model: it has finite memory M and unlimited disk space. Access to one B-size block of disk costs 1 unit, and access to main memory costs 0 units. In this model, sorting takes time O(N/B log_{M/B} N/B) units, where "unit" is one disk access. that's an example of asmyptotic analysis in a realistic model
Suresh Venkat
CC BY-SA 3.0
2011-04-18T04:59:39.440Z
2011-04-18T04:59:39.440Z
Suresh Venkat
<p>Lets imagine we have an algorithm made up of a set of operations. Let assume that it has three kind of operations and the time complexity is  $t(n) = An + Bn\log n + Cn^2$. This algorithm has asymptotic performance $O(n^2)$.</p>

<p>Now, on a real computer (or a more sophisticated abstract machine that doesn't assume infinite capacity, I guess), I eventually hit issues with the complexity of these operations (e.g. a garbage collector, memory paging, cache, ...) which cause $C$ which is a constant in the abstract model to become itself a function of $n$. </p>

<p>Is there a name for this? Is there a framework in which these kinds of issues can be placed?</p>

<p>Obviously from the question and the lack of jargon, I'm a practitioner, not a computer scientist (my PhD was in AI, not CompSci). But the issue is critically important for studying actual algorithm behavior, and so I'd appreciate any help in finding resources that put it into a less ad-hoc context.</p>

CC BY-SA 3.0
2011-04-18T06:43:56.290Z
I don't understand what is the question. Exactly what is the "cross-over point" here?
Jukka Suomela
CC BY-SA 3.0
2011-04-18T08:12:13.560Z
Ian, I tried to make the question more readable based on what I understand from it. Feel free to roll back if you don't find my edit helpful. Based on understanding, you just need a more careful analysis of the time complexity of the algorithm treating those values which are not constant on a real computer as functions of $n$. In my experience, it is sometimes better to state the original problem that we are facing in place of making a formalization, especially when we don't have experience on similar formalizations.
Kaveh
CC BY-SA 3.0
2011-04-18T08:23:09.760Z
My impression is that you have an algorithm and you have analyzed its time complexity but in practice it is performing worst than you expect and you have some ideas about why this is happening.
Kaveh
CC BY-SA 3.0
2011-04-18T20:15:52.443Z
In simple memory models, you do not leave your $\mathcal{O}(.)$ class. Only your constants become very large. I am not sure about more complex models.
Raphael
CC BY-SA 3.0
2011-04-18T20:23:18.533Z
In case you do not know, “jargon” is a derogatory word when it refers to technical terms.  It is acceptable when you refer to the technical terms in your own field (as a kind of self-ridicule), but describing the technical terms in other people’s field as “jargon” may upset some people in that field.
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-19T22:50:10.207Z
Thanks folks. Jukka - The 'cross-over point' is where an implementation of the algorithm scales worse than its big-O. Kaveh - I'm fine with the changes, thanks. Raphael - if your "constants *become* very large" (i.e. if they change), then this isn't encapsulated in the big-O of the algorithm (i.e. in a practical implementation are the constants actually functions of n?). Tsuyoshi - in case you do not know it is rather passive aggressive to pretend to show concern that someone doesn't offend another as a way of voicing your own displeasure at what they've done.
Ian
CC BY-SA 3.0
2011-04-19T23:01:43.550Z
I've removed the bit about a 'cross-over point', because, as Suresh assumed, below, my point is more general: where do I look for ways to make the *practical* scaling of an algorithm less ad-hoc than just big-O plus a bit of experimentation and messing around!
Ian
CC BY-SA 3.0
2011-04-19T23:23:27.167Z
Stated more plainly: Your use of the word “jargon” shows your contempt for theoretical computer science unless you used it without knowing the meaning of the word.  I am mildly offended by it, and I fail to see why you are doing that in the questions to people working in theoretical computer science.  But this is off-topic, and this is my last comment in this thread.
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-19T23:41:25.387Z
Based on your latest edit, your question seems to be unrelated to the use of O-notation. The core of the question seems to be the following: "In abstract models, it is often assumed that the computer can perform an elementary operation (e.g., memory access) in 1 time unit. However, in a real-world system, the complexity of an elementary operation may depend on the size of the input. Is there a theoretical model that captures this phenomenon?"
Jukka Suomela
CC BY-SA 3.0
2011-04-20T04:08:57.263Z
Thank-you for being straight Tsuyoshi. I'm sorry if the word caused you offence. I have no contempt for theoretical computer science. I use 'jargon' to mean 'technical language' not in its pejorative sense. It never occurred to me that it would be taken that way.
Ian
CC BY-SA 3.0
2011-04-20T04:11:53.423Z
Jukka - that's a fair summary. O-notation is the only mechanism I've come across for the former though, so it is significant. As I said in one of my comments, I have lots of books on algorithms that just give the O-notation, and assume I understand the abstractions involved (which I do). That is obviously the baseline. And one where I'm finding the limits in what I am doing. Can you point me at anything that would model reality better?
Ian
CC BY-SA 3.0
2011-04-20T10:23:33.940Z
I am voting to close, as this discussion seems to be related to the misunderstanding that O-notation and abstract models of computation are somehow interrelated. They are not. You can use [O-notation](http://mathworld.wolfram.com/LandauSymbols.html) to describe the growth rate of **any** function (regardless of whether the function models ice cream sales or running times). And of course you can use it to describe the running time equally well for **any** model of computation, realistic or not (Turing machines, RAM model, I/O model, Intel 386 machine language...).
Jukka Suomela
CC BY-SA 3.0
2011-04-20T14:56:45.180Z
Jukka - how about instead of 'voting to close' and answering in a comment, you answer the question? Resolving a misunderstanding is as good an answer as any.
Ian
CC BY-SA 3.0
2011-04-22T19:38:07.703Z
I think you would benefit from looking at the formal definition of $\mathcal{O}$. Having different constant factors for different $n$ is not an issue as long as there is an upper bound on them *in the limit*.
Raphael
CC BY-SA 3.0
2011-04-24T07:09:47.290Z
Raphael, of course. But if you look at the specific example I gave (of C becoming O(n), then you'd see that it would not be still bounded by the same limit).
Ian
<ds.algorithms><reference-request><application-of-theory>
Practical limits of big-O performance scaling
Ian
# Practical limits of big-O performance scaling

(Asked by: username_0 on 2011-04-18)

Lets imagine we have an algorithm made up of a set of operations. Let assume that it has three kind of operations and the time complexity is $t(n) = An + Bn\log n + Cn^2$. This algorithm has asymptotic performance $O(n^2)$.

Now, on a real computer (or a more sophisticated abstract machine that doesn't assume infinite capacity, I guess), I eventually hit issues with the complexity of these operations (e.g. a garbage collector, memory paging, cache, ...) which cause $C$ which is a constant in the abstract model to become itself a function of $n$.

Is there a name for this? Is there a framework in which these kinds of issues can be placed?

Obviously from the question and the lack of jargon, I'm a practitioner, not a computer scientist (my PhD was in AI, not CompSci). But the issue is critically important for studying actual algorithm behavior, and so I'd appreciate any help in finding resources that put it into a less ad-hoc context.

**Tags:** ds.algorithms, reference-request, application-of-theory

> **Comments:**
> **username_1**: I don't understand what is the question. Exactly what is the "cross-over point" here?  
> **username_2**: username_0, I tried to make the question more readable based on what I understand from it. Feel free to roll back if you don't find my edit helpful. Based on understanding, you just need a more careful analysis of the time complexity of the algorithm treating those values which are not constant on a real computer as functions of $n$. In my experience, it is sometimes better to state the original problem that we are facing in place of making a formalization, especially when we don't have experience on similar formalizations.  
> **username_2**: My impression is that you have an algorithm and you have analyzed its time complexity but in practice it is performing worst than you expect and you have some ideas about why this is happening.  
> **username_3**: In simple memory models, you do not leave your $\mathcal{O}(.)$ class. Only your constants become very large. I am not sure about more complex models.  
> **username_4**: In case you do not know, “jargon” is a derogatory word when it refers to technical terms.  It is acceptable when you refer to the technical terms in your own field (as a kind of self-ridicule), but describing the technical terms in other people’s field as “jargon” may upset some people in that field.  
> **username_0**: Thanks folks. Jukka - The 'cross-over point' is where an implementation of the algorithm scales worse than its big-O. username_2 - I'm fine with the changes, thanks. username_3 - if your "constants *become* very large" (i.e. if they change), then this isn't encapsulated in the big-O of the algorithm (i.e. in a practical implementation are the constants actually functions of n?). Tsuyoshi - in case you do not know it is rather passive aggressive to pretend to show concern that someone doesn't offend another as a way of voicing your own displeasure at what they've done.  
> **username_0**: I've removed the bit about a 'cross-over point', because, as Suresh assumed, below, my point is more general: where do I look for ways to make the *practical* scaling of an algorithm less ad-hoc than just big-O plus a bit of experimentation and messing around!  
> **username_4**: Stated more plainly: Your use of the word “jargon” shows your contempt for theoretical computer science unless you used it without knowing the meaning of the word.  I am mildly offended by it, and I fail to see why you are doing that in the questions to people working in theoretical computer science.  But this is off-topic, and this is my last comment in this thread.  
> **username_1**: Based on your latest edit, your question seems to be unrelated to the use of O-notation. The core of the question seems to be the following: "In abstract models, it is often assumed that the computer can perform an elementary operation (e.g., memory access) in 1 time unit. However, in a real-world system, the complexity of an elementary operation may depend on the size of the input. Is there a theoretical model that captures this phenomenon?"  
> **username_0**: Thank-you for being straight Tsuyoshi. I'm sorry if the word caused you offence. I have no contempt for theoretical computer science. I use 'jargon' to mean 'technical language' not in its pejorative sense. It never occurred to me that it would be taken that way.  
> **username_0**: Jukka - that's a fair summary. O-notation is the only mechanism I've come across for the former though, so it is significant. As I said in one of my comments, I have lots of books on algorithms that just give the O-notation, and assume I understand the abstractions involved (which I do). That is obviously the baseline. And one where I'm finding the limits in what I am doing. Can you point me at anything that would model reality better?  
> **username_1**: I am voting to close, as this discussion seems to be related to the misunderstanding that O-notation and abstract models of computation are somehow interrelated. They are not. You can use [O-notation](http://mathworld.wolfram.com/LandauSymbols.html) to describe the growth rate of **any** function (regardless of whether the function models ice cream sales or running times). And of course you can use it to describe the running time equally well for **any** model of computation, realistic or not (Turing machines, RAM model, I/O model, Intel 386 machine language...).  
> **username_0**: Jukka - how about instead of 'voting to close' and answering in a comment, you answer the question? Resolving a misunderstanding is as good an answer as any.  
> **username_3**: I think you would benefit from looking at the formal definition of $\mathcal{O}$. Having different constant factors for different $n$ is not an issue as long as there is an upper bound on them *in the limit*.  
> **username_0**: username_3, of course. But if you look at the specific example I gave (of C becoming O(n), then you'd see that it would not be still bounded by the same limit).  

---

## 3 answers

### Answer by username_7 on 2011-04-18. Score: 10 | Accepted answer

While I'm not entirely sure what you're getting at, there are a number of frameworks that explicitly capture the cost changes that show up when we hit real resource limits. Three examples:

1. the external memory framework that emphasizes the expense of going to disk (idealized by setting main memory reference costs to 0, and disk reference costs to some fixed constant)
2. The cache-oblivious model that assumes an unknown cache size and performance hits for going beyond.
3. The streaming computational model in which only you're only allowed sublinear working storage.

Are these along the lines that you're thinking ?

> **Comments:**
> **username_0**: So this is just a general difference between a theoretical time complexity of the algorithm, and the time complexity of a practical implementation on a more realistic model of an abstract machine? If the former then is big-O notation, does the latter have a name? I've got a shelf full of books that talk about the big-O of various algorithms, and I'm used to calculating the same. Is the more realistic model actually done?  
> **username_7**: I think you have to separate two things. It is the notion of cost that changes when one moves to these models. The rules for how to charge an operation are different, in other words. The big-Oh notation is still used here to describe asymptotic complexity bounds  
> **username_0**: Grrr. I'm feeling dumb now.  I've never seen a big-O given with a description of the abstract machine. Are you saying that for a different machine you'd have a different asymptotic complexity (in which case, this seems odd, because in any finite memory machine, the asymptotic time would be infinite - eventually it would always run out of memory), or are you saying that the big-O is irrelevant, because the algorithm needs to be fed through a more realistic model of the computer to find some actual expected performance (in which case, that's exactly what I'd love to learn more about).  
> **username_6**: Big O does come with description of abstract machine, probably RAM model. But if you want to understand how the effects of realistic model affects the Big-O you may want to refer some paper on such model like Cache Oblivious http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.2225&rep=rep1&type=pdf  
> **username_7**: Consider the external memory model: it has finite memory M and unlimited disk space. Access to one B-size block of disk costs 1 unit, and access to main memory costs 0 units. In this model, sorting takes time O(N/B log_{M/B} N/B) units, where "unit" is one disk access. that's an example of asmyptotic analysis in a realistic model  

---

### Answer by username_5 on 2011-04-20. Score: 0

If 'C' isn't constant in your real-world application, then the abstract model you're apply isn't meaningful anymore. The abstraction isn't broken; you're just using the wrong one.

The thing about abstractions is that you can make them as precise or as vague as you need them to be for your application. You could say "This algorithm has time complexity of at least 0 and at most never terminates." It would be correct, but it's so abstract that it's completely useless. If C is growing with 'n' rather than being constant, then the algorithm you're analyzing is now a new algorithm. Figure out how C is growing in relation to N, drop it into your expression and do the algebra. Voila; your expression is now more meaningful.

You can analyze an algorithm all day long, but if it doesn't represent what's actually happening, then you're not doing yourself any good. There isn't any special name for this: it's just a matter of garbage-in; garbage-out.

> **Comments:**
> **username_6**: How does this answer the question? The person asking the question is aware of the abstractions or in this case idealistic computation model problem. He is asking for realistic models which are under research or practice.  
> **username_0**: That is actually quite helpful, username_5. But I don't believe it is just a matter of giving up. The comments on here are helping me clarify that what I am asking for is more information on exactly these other abstractions. Also, your example is a little odd, because big-O time complexity is never given as a range, for deterministic algorithms, in my experience. [Sai - exactly, thanks!]  
> **username_5**: @username_0 You might want a different Bachmann–Landau notation for that, then. 'Big-Omega' for the lower-bound or 'Big-Theta' for a function bounded both above and below.  
> **username_5**: @username_0 your answer is quite useful, however. Thank you =)  

---

### Answer by username_0 on 2011-04-20. Score: 0

**What Big-O Means**

Big-O notation, or [Landau Symbols](http://mathworld.wolfram.com/LandauSymbols.html), are not particular to any model of computation, or even to computer science. When used to illustrate the asymptotic complexity of an algorithm, they are always given relative to some model of an abstract machine, even if that abstraction isn't made explicit.

In texts on algorithms the model used is often a [RAM machine](http://en.wikipedia.org/wiki/Random_access_machine), and usually is used without explicit acknowledgement (see for example the unqualified use of big-O notation on the wikipedia pages for [Quicksort](http://en.wikipedia.org/wiki/Quicksort) or [Dijkstra's Algorithm](http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm), or the examples in the [Table of Common Time Complexities](http://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities)).

On a different machine model, or on a real machine, the scaling properties will be different. With a suitable model of computation, one could derive the asymptotic performance and state it in big-O notation, and the result may be different to that for the RAM machine and therefore to commonly published big-O values.

For example: on a machine with sequential memory (a Turing Machine with a single tape, say), binary search no longer has a running time O(log n) - the commonly cited result for a RAM machine - because traversing the tape requires O(n) time.

As a second example, [this chapter](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.2225&rep=rep1&type=pdf) shows an explicit computational model described, and used to derive the asymptotic performance of various algorithms.

**Realistic Performance Envelopes**

Analysing the asymptotic complexity of an algorithm makes the assumption that the algorithm would still be viable regardless of the problem size. But ultimately, no real machine can cope with infinite size problems. So unless the algorithm is O(1) in time and space, there will always come a point beyond which the performance of the algorithm is limited by the capacity of the machine, rather than the theoretical complexity bound.

It would be perfectly possible to analyse the algorithm (using a realistic model of a resource-limited machine) to determine the maximum solvable problem size. And if the real machine went through different modes of computation at different problem sizes (for example, it stops being able to hold data in cache at a particular size, then stops being able to hold it in RAM, then runs out of disk space, etc), one could work out where these transitions would occur, and give a more detailed characterization of its performance envelope. These kinds of analysis might be important if you need to make guarantees about real-world performance, but are completely unrelated to asymptotic performance analysis.

There isn't a special big-O like notation for those results, you would just give the equations for the performance explicitly. Given that you are now dealing with explicit upper bounds, big-O notation would be inappropriate.

> **Comments:**
> **username_0**: I've brought citations and insights from your comments into this answer, as a summary - please let me know if I've got the wrong end of the stick anywhere. I appreciate your help, but I want to make sure that the question has a useful answer, because I know stack exchange often come up high on google searches.  
> **username_7**: I don't understand why you use "big-0 is not useful" when you cross machine model boundaries. What breaks down is the particular abstraction you're using. Big-Oh is NOTATION, not truth.  
> **username_0**: I didn't use it at that point. I used it at the point that I talked about a real machine with a finite capability. But I take your point.  
> **username_7**: I feel this discussion is getting rapidly out of scope, but I'm not even sure why you'd say 'asymptotic complexity is not useful'. That is again a concept - a way of describing complexity. The failure here is a failure of the model to adjust to real-life scaling.  
> **username_0**: @Suresh - I don't mind getting out of scope - I learn a lot about my poor concept-space from bumping up against these objections to my vague language. Maybe it isn't helpful for others, but it is always helpful to me! ... That said, surely asymptotic measures of anything cease to be useful at the point where there is a real hard limit. For any real computer, there will be a limit to the problem size. That's all I mean. If there's a better way to phrase it, I'm happy to edit. For now I'll just remove that sentence. Thanks again.  
> **username_8**: To be pedantic, **binary search cannot be O(log n)**, for the trivial reason that binary search is not a function from the integers to the integers.  The *running time* of binary search is O(log n) in the standard RAM model and is O(n) in the single-tape Turing machine model.  
> **username_3**: Of course asymptotics are only approximations for finite realities. But that is what we do in (T)CS: Finding abstract models you can work with for awefully intricate real problems/machines.  

---

