<p>I recently followed a course on complexity theory and according to the professor I got one particular question wrong. The question involved the runtime complexity of checking the correctness of a graph colouring, which I had answered would be O(m) (simply check whether each edge in the graph consists of two differently coloured vertices). However, they said it should be O(nm). When I tried to get an explanation of this I got:</p>
<p>&quot;We have read your comments on your views on computational complexity and O(.)-analyzes, and have the impression that you may be building on knowledge learned in applied computer science courses. These analyses make domain specific assumptions which do (or need) not hold in the general/abstract case (which was what (TA)’s remark in his earlier response tried to express). In this course we take a theoretical computer science perspective, and any O(.)-analysis claim needs to be argued in a self-contained and solid manner in the assignment and meet the standards of theoretical complexity theory. (TA)’s feedback on your answers should be understood in this light. &quot;</p>
<p>Which did not really clear it up to me. Could someone shed light on this distinction?</p>

CC BY-SA 4.0
2022-06-26T15:47:55.507Z
Answer to question in title: implied constants in big O notation. If the explicit bound conveyed by the theoretically nice $O(n)$ is actually $10^{100}n$, then this $O(n)$ bound is definitely not useful in applied settings.
mathworker21
CC BY-SA 4.0
2022-06-26T16:55:34.360Z
It is hard to glean the proper context for the question without more details. The instructors seem to suggest that one should be more careful about the specification of the algorithm/implementation and the formal analysis when doing a theoretical course. A canonical example where this shows up in undergraduate algorithm classes is in the use of hashing. Hashing is used liberally in applied courses with the implicit understanding that it takes O(1) time while theory courses will not let you do this.
Chandra Chekuri
<cc.complexity-theory><graph-theory>
What's the difference between 'theoretical' and 'applied' runtime complexity?
Rule
# What's the difference between 'theoretical' and 'applied' runtime complexity?

(Asked by: username_0 on 2022-06-26)

I recently followed a course on complexity theory and according to the professor I got one particular question wrong. The question involved the runtime complexity of checking the correctness of a graph colouring, which I had answered would be O(m) (simply check whether each edge in the graph consists of two differently coloured vertices). However, they said it should be O(nm). When I tried to get an explanation of this I got:

"We have read your comments on your views on computational complexity and O(.)-analyzes, and have the impression that you may be building on knowledge learned in applied computer science courses. These analyses make domain specific assumptions which do (or need) not hold in the general/abstract case (which was what (TA)’s remark in his earlier response tried to express). In this course we take a theoretical computer science perspective, and any O(.)-analysis claim needs to be argued in a self-contained and solid manner in the assignment and meet the standards of theoretical complexity theory. (TA)’s feedback on your answers should be understood in this light. "

Which did not really clear it up to me. Could someone shed light on this distinction?

**Tags:** cc.complexity-theory, graph-theory

> **Comments:**
> **username_1**: Answer to question in title: implied constants in big O notation. If the explicit bound conveyed by the theoretically nice $O(n)$ is actually $10^{100}n$, then this $O(n)$ bound is definitely not useful in applied settings.  
> **username_2**: It is hard to glean the proper context for the question without more details. The instructors seem to suggest that one should be more careful about the specification of the algorithm/implementation and the formal analysis when doing a theoretical course. A canonical example where this shows up in undergraduate algorithm classes is in the use of hashing. Hashing is used liberally in applied courses with the implicit understanding that it takes O(1) time while theory courses will not let you do this.  

---

## 0 answers

