Skip to main content
jsguy's user avatar
jsguy's user avatar
jsguy's user avatar
jsguy
  • Member for 9 years, 9 months
  • Last seen more than 5 years ago
11 votes
1 answer
2k views

What does sublinear space mean for Turing machines?

9 votes
1 answer
930 views

$O(\frac{\log n}{\log \log n})$ algorithm for the prefix parity problem

8 votes
1 answer
3k views

Is radix sort really O(n) for sorting 32 bit integers?

6 votes
1 answer
877 views

What are some interesting applications of the skyline problem?

6 votes
1 answer
463 views

Given an array of size N, if you know that all of the elements are white except for one, how to find the index of that element efficiently?

5 votes
2 answers
3k views

Verifying whether a description of a shortest path tree is actually the shortest path tree in O(V+E) time

4 votes
1 answer
900 views

2 approximation algorithm for the single machine scheduling problem

4 votes
2 answers
1k views

Why are decision problems easier than the equivallent optimization problems?

3 votes
1 answer
619 views

I/O cost to traverse a tree stored in preorder form

3 votes
1 answer
170 views

Where would someone find amortized analysis more useful than average analysis and the opposite?

2 votes
1 answer
418 views

Asymptotic runtime for querying an interval tree

2 votes
1 answer
81 views

Why is $O(\log_{M/B} N/M)$ the same as $O(\log_{M/B} N/B)$?

2 votes
1 answer
216 views

Is an algorithm in pseudocode a reasonable way to establish complexity?

2 votes
1 answer
4k views

Updating the MST of a graph G = (V,E) when decreasing the weight of one of the edges that is not part of the MST

2 votes
1 answer
748 views

Supporting queries for finding how many intervals in a dynamic set of 1D intervals contain a given point

2 votes
1 answer
68 views

Is it possible to come up with a graph instance that would force Dijkstra to perform a decrease key on every single edge?

2 votes
1 answer
567 views

Question on the properties of red black trees

1 vote
1 answer
124 views

Why do I need a base case for n=3 when solving a d&c recurrence?

1 vote
1 answer
189 views

Solving the graph colourability problem in polynomial time if the equivallent decision problem is in $P$ [duplicate]

1 vote
1 answer
1k views

How would you implement truly random hash functions in practice?

1 vote
1 answer
70 views

Using B trees to search inside dynamically changing array segments

1 vote
1 answer
3k views

Approximation algorithm for the partition problem

1 vote
1 answer
152 views

Who was the first to define the RAM model?

1 vote
1 answer
1k views

How to simulate a k tape non deterministic turing machine with 2 tapes?

1 vote
1 answer
1k views

Understanding a proof in the sweep line algorithm when finding all line segment intersections

1 vote
1 answer
4k views

I can not see why MSD radix sort is theoretically as efficient as LSD radix sort

1 vote
0 answers
584 views

Potential method analysis for Insert and Extract-max on a Max heap data structure

1 vote
1 answer
364 views

How to prove strict space lower bounds using crossing sequences in Turing machines?

1 vote
2 answers
155 views

How to show whether $n2^n = 2^{O(n)}$?

1 vote
1 answer
903 views

Why is the orthogonal line segment intersection algorithm $O(n\log n+R)$ instead of $O(n\log n + Rn)$?