Hacker Newsnew | comments | show | ask | jobs | submit login

Your first paragraph is also a slight misunderstanding of big O notation. In fact, the notation allows to make general comparisons between the growth rates of arbitrary functions, not necessarily referring to time complexities of algorithms (although that is a frequent use of big-O notation). For example, sometimes you use big O to express the amount of space an algorithm uses, sometimes you just count some objects with a certain property, etc.

When it comes to time complexity, one always has to clarify what is the computational model assumed. What are the allowed operations? What are we counting? Are we counting the number of comparisons between arbitrary (comparable) elements? Are we counting operations on bits? Are we counting arithmetic operations on numbers that fit in a register of some idealized computer? Of course if the model is not agreed upon, the answers can differ, as in your example.

Once the model is clear, and you want to express the running time of an algorithm, the result can in fact depend on both input size and input value (although this distinction makes more sense in certain models than in others). An example is the Ford-Fulkerson algorithm for max flow, whose running time (in the RAM model) depends both on the size of the network and the value of the max flow.




> In fact, the notation allows to make general comparisons between the growth rates of arbitrary functions, not necessarily referring to time complexities of algorithms (although that is a frequent use of big-O notation).

True, I was simplifying by restricting to the context the OP was asking about (time complexity of an algorithm).

-----


Yes, I didn't mean to sound pedantic - just meant that there is no single way to measure time complexity of algorithms - when we talk about sorting, often we assume the comparison model: only comparisons between elements count, and we can't do any arithmetic on the elements - then we have O(n log n). In another model we assume the elements are numbers of reasonable size and we can operate on them in constant time (a somewhat realistic model of a CPU) - then we can sort in O(n).

That's why I think it is good practice to separate the understanding of the mathematical concept from the study of algorithms and just be clear about what we are counting.

-----


I get your point now, and it is indeed an excellent one to make.

-----




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: