Jeremy Hurwitz
Reputation
Next privilege 2,000 Rep.
Edit questions and answers
 Jan 4 awarded Populist Jul 27 awarded Yearling Apr 4 comment Meaning of amortized analysis of an algorithm Thanks, @hengxin. Fixed. Apr 4 revised Meaning of amortized analysis of an algorithm add missing subscripts Mar 19 awarded Nice Answer Aug 3 comment Computation with a memory wiped computer @Pastafarianist, that's an excellent question. It took me longer than I'd like to admit to figure it out. The short answer is that it's hidden in the recursion, specifically AND(f1, AND(f2, f3)). To compute R3<--R3+f1f2R1, we need the same value to be in R1 in lines 1 and 3. So the intermediate results from lines 1 and 2 must be stored in R2 and R3. Now look at the recursion in line 2, and suppose f2=AND(g1,g2). When computing f2, R2 is now the register that must remain fixed, so the intermediate results for g1 and g2 are stored in R1 and R3. Jul 27 awarded Yearling Jul 16 awarded Good Answer Jul 27 awarded Yearling Jul 24 awarded Nice Answer Nov 13 answered Meaning of amortized analysis of an algorithm Nov 1 comment Can a graph be non 3-colourable without having k4 as a sub graph? Sorry! That should have said "square with one diagonal". I've fixed it. Nov 1 revised Can a graph be non 3-colourable without having k4 as a sub graph? edited body Oct 31 comment Can a graph be non 3-colourable without having k4 as a sub graph? In general, there's no "easy" characterization of 3-colorability. Determining whether a graph is 3-colorable is NP-complete, so no characterization can be in P (such as checking whether it contains $K_4$, which is $O(n^4)$). Oct 31 answered Can a graph be non 3-colourable without having k4 as a sub graph? Oct 27 comment Computational Complexity of Modular Exponentiation On the wikipedia page, the input is described as "Two $n$-digit numbers". So $\Theta(n)$ is linear in the length of the input. In general, whenever you read a running time, always ask yourself what the $n$ is referring two -- both (1) the number of bits and (2) the value being represented are common idioms, so you need to decide based on context which is being used. Oct 24 answered Computational Complexity of Modular Exponentiation Jul 27 awarded Yearling Jul 15 comment Time complexity to calculate a digit in a decimal Champernowne's constant can be computed in real-time. See rjlipton.wordpress.com/2012/06/04/…. Jul 15 answered Time complexity to calculate a digit in a decimal