0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't understand what is the question. Exactly what is the "cross-over point" here? $\endgroup$ – Jukka Suomela Apr 18 '11 at 6:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Apr 18 '11 at 8:12
  • 2
    $\begingroup$ 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. $\endgroup$ – Kaveh Apr 18 '11 at 8:23
  • 2
    $\begingroup$ 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?" $\endgroup$ – Jukka Suomela Apr 19 '11 at 23:41
  • 4
    $\begingroup$ 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 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...). $\endgroup$ – Jukka Suomela Apr 20 '11 at 10:23
10
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Ian Apr 19 '11 at 22:57
  • 5
    $\begingroup$ 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 $\endgroup$ – Suresh Venkat Apr 20 '11 at 0:08
  • $\begingroup$ 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). $\endgroup$ – Ian Apr 20 '11 at 4:24
  • 2
    $\begingroup$ 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 citeseerx.ist.psu.edu/viewdoc/… $\endgroup$ – Sai Venkat Apr 20 '11 at 4:38
  • 3
    $\begingroup$ 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 $\endgroup$ – Suresh Venkat Apr 20 '11 at 6:11
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Sai Venkat Apr 20 '11 at 4:24
  • 1
    $\begingroup$ 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!] $\endgroup$ – Ian Apr 20 '11 at 4:29
  • $\begingroup$ @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. $\endgroup$ – Joe Apr 20 '11 at 17:09
  • $\begingroup$ @Ian your answer is quite useful, however. Thank you =) $\endgroup$ – Joe Apr 20 '11 at 17:19
0
$\begingroup$

What Big-O Means

Big-O notation, or Landau Symbols, 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, and usually is used without explicit acknowledgement (see for example the unqualified use of big-O notation on the wikipedia pages for Quicksort or Dijkstra's Algorithm, or the examples in the 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 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ian Apr 20 '11 at 15:43
  • 3
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Apr 20 '11 at 15:57
  • $\begingroup$ 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. $\endgroup$ – Ian Apr 20 '11 at 17:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Apr 20 '11 at 19:13
  • 3
    $\begingroup$ 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. $\endgroup$ – Jeffε Apr 21 '11 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.