Reputation
1,201
Next privilege 2,000 Rep.
Edit questions and answers
Badges
1 6 12
Newest
 Populist
Impact
~29k people reached

  • 0 posts edited
  • 0 helpful flags
  • 18 votes cast
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