# Questions tagged [notation]

Use this tag whenever you have a question about what some particular symbol/notation means.

17 questions
Filter by
Sorted by
Tagged with
I have been reading a couple of texts on operational semantics. In [1], the evaluation of expressions is done as in this rule: $\frac{<e_1,s>\;\Rightarrow \;n_1\;\;\;<e_2,s>\;\Rightarrow ... 10answers 11k views ### O(·) is not a function, so how can a function be equal to it? I totally understand what big$O$notation means. My issue is when we say$T(n)=O(f(n))$, where$T(n)$is running time of an algorithm on input of size$n$. I understand semantics of it. But$T(n)$... 2answers 11k views ### Operator precedence in propositional logic there is some kind of priorities for the elements in propositional logic ? for example : p ∧¬q → r , given this ,we there may be two options (p ∧¬q) → r OR p ∧ (¬q → r) , which one is the correct ?... 1answer 83 views ### In type systems, is there a name for SQL's way of cutting and combining record types into new types? I'd like to have this feature in my application programming language (which these days, is Scala), but when I went to learn more about it on the internets, I realized I don't know the name of it. I'm ... 1answer 88 views ### Exact meaning of$2^{\mathcal{O}(f(n))}$In Sipser's Introduction to the Theory of Computation he uses the notation$2^{\mathcal{O}(f(n))}$to denote some asymptotic running time. For example he says that the running time of a single-tape ... 1answer 210 views ### For complexity classes A and B, what does$A^B$mean? What does$A^B$mean where A and B are complexity classes? The "Polynomial Hierarchy" page says:$A^B$is the set of decision problems solvable by a Turing machine in class A augmented by an oracle ... 2answers 7k views ### Order of growth definition from Reynolds & Tymann I am reading a book called Principles of Computer Science (2008), by Carl Reynolds and Paul Tymann (published by Schaum's Outlines). The second chapter introduces algorithms with an example of a ... 2answers 3k views ### What is this fraction-like “discrete mathematics”–style notation used for formal rules? In the paper "A Conflict-Free Replicated JSON Datatype", I encountered this notation for formally defining "rules": What is this notation called? How do I read it? For example: the ... 1answer 7k views ### Can a Big-Oh time complexity contain more than one variable? Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct ... 1answer 732 views ### What does > mean in this TAOCP solution? For our assignment we have to implement a solution given to one of the problems in The Art of Computer Programming by D.E. Knuth (Ex24; Chapter 5: Sorting; TAOCP, Vol3, 2nd). However, I fail to ... 1answer 174 views ### What does$n^{O(1)}$mean? I read an example that said explain what "$f(n)$is$n^{O(1)}$" means. I can't interpret the$n^{O(1)}$syntax. I know what Big$O$notation is, its just that this example looks odd to me. 2answers 86 views ### Origins of misconception about using equality signs with Landau notation From "Misconception 1" from Søren S. Pedersen's blog, and as many have seen before, a major misconception in Big-O (and others) notation is to say a function is "equal" to Big-O of some other function:... 1answer 462 views ### How I can find all equivalence classes by Myhill-Nerode? first of all I'm sorry for my bad English and second I'm sorry for my mistakes of understanding the following topic, I still going to school and learning this for interest. The topic is Myhill-Nerode ... 2answers 365 views ### How do I interpret this divide and conquer algorithm for removing duplicates in a list? Consider the following divide and conquer algorithm to remove duplicates in a list. The text is in French. What is the meaning of the variables$c1, c2, d1, d2$? Why are only the variables$c1, d1$... 2answers 1k views ### What is the origin of λ for empty string? I usually use the symbol$\varepsilon$for empty string (empty word or null string). But I know some people use$\lambda$instead of$\varepsilon$. I think$\varepsilon$is derived from the word "... 1answer 118 views ### Hierarchy of complexity classes$\bigcup_{c > 0} \mathrm{Time}(2^{c \log^k n})$, w.r.t.$k$This is a true/false question: For each integer$k > 1$, define the complexity class$\sf QP_k := \bigcup_{c > 0} Time(2^{c \log^k n})$. Then for all integers$k > 1$,$\sf QP_k \subsetneq ...
Is the class of problems with complexity $O(n^{n^\epsilon})$ at every $\epsilon>0$ same as class of problems with complexity $O(n^{f(n)})$ at every $f(n)\in\omega(1)$ and hence both classes are ...