Intuitively, you can think of a binary indexed tree as a compressed representation of a binary tree that is itself an optimization of a standard array representation. This answer goes into one ...

The complete picture is fairly complicated. There are many layers built on top of one another that collectively implement high-level abstractions on top of electrical voltages. There is no simple ...

To add to the automata-based transformations described above, you can also prove that regular languages are closed under reversal by showing how to convert a regular expression for $L$ into a regular ...

All regular languages have LL(1) grammars. To obtain such a grammar, take any DFA for the regular language (perhaps by doing the subset construction on the NFA obtained from the regular expression), ...

Consider the TM that always moves the tape head to the right and prints a special non-blank tape symbol at each step. This means that the TM never halts, since it always moves to the right, and never ...

I think it depends on what you're interested in. If you're looking for an exact solution to a problem and you hear that it's either NP-hard or PSPACE-hard, then in either case you won't be able to ...

You noted in your question that $n^n$ grows faster than $n!$, and that’s a great starting point for comparing the growth of $2^{3^n}$ and $n!$. Specifically, let’s ask - of $n^n$ and $2^{3^n}$, which ...

There are actually all sorts of cases where $\log n$ gets way bigger than 100. For example, if you're working with variable-length integers - say, for cryptography - $\log n$ represents the number of ...

I did a quick read over the paper you linked. Based on the ideas given in that paper, here's a simple data structure that obtains an $O(\frac{\log n}{\log\log n})$ time bound on each operation. You ...

In most cases, it's safe to drop the base of the logarithm because, as other answers have pointed out, the change-of-basis formula for logarithms means that all logarithms are constant multiples of ...

Big-$O$ and big-$\Theta$ notations hide coefficients of the leading term, so if you have two functions that are both $\Theta(n^2)$ you cannot compare their absolute values without looking at the ...

Sedgewick and Flajolet have done extensive work in analytic combinatorics, which allows recurrences to be solved asymptotically using a combination of generating functions and complex analysis. Their ...

I believe the goal of this construction is to try to assign true or false to each variable. The color assigned to x will determine whether it's true or false, and there's an edge from x to ¬x to ...

If you are storing a matrix of 0's and 1's, you could consider using a bitvector for storage. This can pack some fixed number of bits (say, 32 bits or 64 bits) into a single integer, which decreases ...

I think that you can prove that BPCP is NP-complete by using a reduction similar to the one used to prove its undecidability. We will directly prove that BPCP is NP-complete by showing how to reduce ...

heap- Since the best and worst case are the same does it not matter the input order? The number of comparisons and assignments will always be the same? I imagine in a heap sort it may be the same ...

Part of the issue with the idea of "proving" the Church-Turing thesis is that the Church-Turing thesis isn't a precise mathematical statement. Rather, it's the idea, or "belief" if you will, that any ...

Imagine having a tournament made of the array elements. Group the array elements into pairs, then compare each pair. Put the larger numbers into one group and the smallers number into another group. ...

No NP-complete problems are known to be in P. If there is a polynomial-time algorithm for any NP-complete problem, then P = NP, because any problem in NP has a polynomial-time reduction to each NP-...

You've asked two questions: Why is the tree height Θ(log n)? Why is the runtime Θ(m log n)? This answer addresses both questions. I'll start off with a review of the ranks of the ...

A quick note: the runtime is not guaranteed to be $O(m \log n)$. For example, suppose that your forest consists of $\sqrt{n}$ a linked lists, each of which has $\sqrt{n}$ nodes in it. Doing a total of ...

Yes, this is decidable. There's a rather direct conversion from a regular grammar to an NFA. From there, run the subset construction to turn the NFAs into DFAs. Run minimization algorithms to convert ...

Think about what happens when you move from one layer in the tree to the next. When you start getting to layers with progressively more nodes, you'll eventually get to a spot where the layers are so ...

I went and asked Don Knuth about this. He mentioned that he first used the new terminology in his 1972 paper Top-Down Syntax Analysis (link here) to provide a consistency between the terminology in $... View answer 5 votes The ideas in this answer come directly from Ricky Demer. I wanted to write a more long-form answer that fills in a few of the details and justifies why this new complexity class is equal to RE. First,... View answer 4 votes Another way to arrive at a solution here - you might recognize that this language is regular, since, intuitively, you’d only need to remember whether you’d seen zero a’s, one a, or two or more a’s. ... View answer Accepted answer 4 votes I've often found that, with problems like these, it's easiest to reason by analogy to software, since anything you can do with a computer you can do with a TM and vice versa (with a giant asterisk). ... View answer 4 votes If you think of the DAG as a graph whose reachability relation is a partial order relation, then an element with that property would be a minimum element in that relation. I haven't seen the term "... View answer 4 votes The most comically slowly-growing function I've ever seriously seen used in a paper is$\alpha^*(n)$, the number of times you have to apply the Ackermann inverse to drop$n\$ to some fixed constant. It'...