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
22 votes
2 answers
887 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 ...
Markus Jalsenius's user avatar
8 votes
1 answer
552 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 ...
J..y B..y's user avatar
  • 2,766
0 votes
2 answers
5k 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 ...
Tony The Lion's user avatar
44 votes
7 answers
5k 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.
Shane's user avatar
  • 2,233

1
5 6 7 8
9