Questions tagged [time-complexity]

Time complexity of decision problems or relations among time-bounded complexity classes. (Use the [analysis-of-algorithms] tag for the time taken by particular algorithms.)

Filter by
Sorted by
Tagged with
9 votes
1 answer
1k views

Quickly finding empty-string producing nonterminals in a CFG

For a given context free language G, we call a nonterminal $A_i$ nullable if $A_i \rightarrow^* \epsilon$, ie we can derive the empty string from $A_i$ after applying a finite number of productions. ...
user avatar
5 votes
1 answer
500 views

What is the running time of taking a limit?

I'm interested in finding the running time(s) for determining mathematical limits. For instance, $\lim_{x \to 2} \frac{1}{x} = \frac{1}{2}$. I'd like to know more about algorithms for determining ...
user avatar
  • 2,080
22 votes
1 answer
1k views

Binary multiplication and parity convolution

This question is about the relationship between normal multiplication of binary numbers and polynomial multiplication mod 2. To make the question concrete, I would ideally like to know if there is a ...
user avatar
  • 3,920
22 votes
2 answers
866 views

Multiplicative version of 3-SUM

What is known about the time complexity of the following problem, which we call 3-MUL? Given a set $S$ of $n$ integers, are there elements $a,b,c\in S$ such that $ab=c$? This problem is similar to ...
user avatar
8 votes
1 answer
551 views

Analysis of the synergy of two algorithms in comparison to their simulation in parallel

Consider the following two algorithms for searching in a sorted array of $n$ elements: A) interpolation search and binary search simulated in parallel, and B) search through alternating ...
user avatar
  • 2,391
0 votes
2 answers
4k views

Linked List size in constant time or linear time [closed]

The space-time complexity of getting the size of the linked list can differ in different implementations as far as I understand it. In the Boost C++ library one finds that the size() function can be ...
user avatar
44 votes
7 answers
4k views

Using lambda calculus to derive time complexity?

Are there any benefits to calculating the time complexity of an algorithm using lambda calculus? Or is there another system designed for this purpose? Any references would be appreciated.
user avatar
  • 2,213

1
4 5 6 7
8