the amount of time resources (number of atomic operations or machine steps) required to solve a problem or run an algorithm with respect to the input size.

learn more… | top users | synonyms

3
votes
1answer
26 views

Proving complexity of computing product of matrices

If $A$ is a non-singular $n\times n$ matrix, $B$ is an $n\times p$ matrix, and $C$ is a $p\times n$ matrix (where $1\le p \ll n$), how does one prove that the complexity of $$D=A^{-1}(BC)$$ is $\frac{...
1
vote
1answer
23 views

Complexity of matrix inverse via Gaussian elimination

I'm trying to determine the exact complexity of finding an $n\times n$ matrix inverse of $A$. If it is known that the complexity of Gaussian elimination is $\frac{2}{3}n^3 + \frac{1}{2}n^2+O(n)$, then ...
1
vote
1answer
38 views

Time complexity of the fast exponentiation method

I am trying to analyse the time complexity of the fast exponentiation method, which is given as $$x^n= \begin{cases} x^\frac{n}{2}.x^\frac{n}{2} &\text{if n is even}\newline x.x^{n-1} &...
0
votes
1answer
59 views

Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P?

Just as the title says: Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P? Additionally, if one could show that a ...
7
votes
1answer
93 views

Following yesterday's StackOverflow outage - is regular expression matching really difficult, or is the implementation simply inefficient?

Yesterday StackOverflow was down for half an hour. Later, they wrote a blog post about it, detailing that the problem stemmed from unexpectedly high complexity of regular expression matching. In ...
2
votes
2answers
36 views

Does 'subexponential algorithm' refer to input or number of bits used to represent input?

When an algorithm is said to be subexponential - does this refer to the input N or the number of bits used to represent N? Consider the following: trial division for integer factorization (i.e. try ...
0
votes
1answer
25 views

General number field sieve is slower then exhaustive search for 'small' numbers?

In an attempt to understand the efficiency of the GNFS, I've been looking at runtimes. The calculations seem to indicate the GNFS runs slower than exhaustive search for smallish n. For example: ...
1
vote
3answers
38 views

Count elements in the real world in constant time by weighing them

I suppose that counting n elements should be linear time, right? It takes double time to count double number of elements. But in the real world, it is faster and O(1) to weigh elements and find out ...
2
votes
1answer
25 views

Is the runtime for the general number sieve given in base 10, e or 2?

When the runtime of the GNFS is given as e^(64/9*b(log b)^2)^1/3, what base is the log? I'm assuming its e, but other options would obviously be 10 and 2.
0
votes
0answers
35 views

How to schedule different elements in a 24h range?

Given the following conditions: An element has: A time range, for example: 9:00 to 18:00. A repeat time, for example: every 5 minutes. Then a device recieves some elements and has to schedule ...
3
votes
1answer
25 views

Efficient algorithm for graph canonization for directed acyclic graphs?

I'm interesting in generating directed acyclic graphs (see here, for example). As part of this search, I'm curious if there are any efficient algorithms for determining a canonization of a directed ...
5
votes
5answers
186 views

Why does restricting size of input for NP complete problem imply a runtime of O(1)?

I've seen this statement mentioned a few times here on cs.stackexchange and have not been able to follow the logic. The statement is 'If you restrict the input size of the problem then solving that ...
1
vote
0answers
27 views

Single-tape Universal Turing Machine time complexity

When studying the time-hierarchy and space-hierarchy theorems, the main idea is to use a simulation by the universal TM. It is mentioned that the time bound is increased by a logarithmic factor while ...
-2
votes
1answer
467 views

Can we evaluate a polynomial of degree N modulo M at all M points, faster than Θ(mn) time?

Given a polynomial $P(x)$ of degree $N$, evaluate $P(x) \bmod M$ at $x = 0$ to $M-1$, where $M$ is a prime number of order $10^6$. Can we do any better than $O(NM)$ given the constraints we only need ...
0
votes
0answers
28 views

Are there any methods to quantify complexity of finite problems?

On page 348 of "Sipser M. Introduction to the Theory of Computation. Cengage Learning; 2012 Jun 27", it says Perhaps at some time in the future, methods that can quantify the complexity of finite ...
4
votes
2answers
93 views

Do Oracles run in O(1) or O(n) time?

The common understanding of what oracle does is that it answers a question after a single operation. So at first glance, it runs in $O(1)$. But, doesn't it need to actually read the input? Wouldn't ...
1
vote
0answers
18 views

Space-time tradeoffs for deterministic logarithmic space algorithms

I have several algorithms that map read-only input into write-only output utilizing only logarithmic space with pointer arithmetic. While the algorithms have a very small $O(\log^c{}n)$ critical path ...
1
vote
2answers
78 views

Problems that become far easier when restricted to only integer values

I know that there are some problems that are very hard to solve in general, but become much easier and asymptotically faster if restricted to only integer values. One such example would be sorting ...
1
vote
1answer
101 views

Why doesn't subset sum solution violate Exponential Time Hypothesis?

The quickest algorithm for solving subset sum currently is $2^{n/2}$ (via Wiki). Why doesn't this violate the Exponential Time Hypothesis which states that “there is no family of algorithms that can ...
3
votes
2answers
109 views

What would NP-complete solution in O(2^N/B) mean?

Suppose we had an algorithm that solved an NP-complete problem (SAT, TSP, etc.) in time $O(2^{N/B})$ where $B>2$ is an input to the algorithm, along with the instance to be solved. So for $B < ...
0
votes
1answer
29 views

Comparison of running times: Determine largest n to run in given time

I am browsing the "Introduction to Algorithms" book by Thomas H. Cormen. One of the very first tasks in the introduction chapter gives a couple of running time functions like ...
5
votes
3answers
115 views

Is $\Omega(\sqrt{n}!)=\Omega(2^{\sqrt{n}})$ correct?

I'm very confused when I see the following statement in the famous CLRS book "Introduction to Algorithms (3rd)", ch34.2, page 1063: ...and therefore the running time is $\Omega(m!)=\Omega(\sqrt{n}!...
-2
votes
1answer
33 views

Knapsack: there is a polynomial solution in bit terms?

I'm reading about Knapsack problem. The approaches to solve that I found: Branch and bound Brute force Dynamic programming Memory functions Greedy All solutions have exponential time in terms of ...
0
votes
1answer
45 views

Is it always possible to convert a k-tape Turing machine to a single-tape one without increasing its running time complexity exponentially?

I am studying the past exam paper of course Theory of Computation. I know it is always possible to convert a k-tape Turing machine to a single-tape one, but how will the running time complexity be ...
1
vote
1answer
72 views

Is there a way to determine if a collection is a palindrome within a time bound?

I'm learning about data structures, and there's a problem where, given a collection of words $X = (x_1, x_2, \dots, x_n)$ (can include duplicates), I have to find out if it's a palindrome or not. I'm ...
1
vote
1answer
99 views

Prove or disprove that DTIME(n^2)=NL

I need to prove or disprove $DTIME(n^2)=NL$. It kind of feel obvious that I need to disprove it, because if I have non-deterministic machine $M$ that uses $\log n$ space, then it meets at most $|Q| n\...
1
vote
1answer
19 views

Example Turing Machine for a time-constructible function

I am currently reading "Computation Complexity: A Modern Approach" by Arora and Barak and have a question about time-constructible functions. In particular, I can't construct a turing machine for a ...
0
votes
1answer
44 views

Is finding all cycles in a graph using some version of Johnson's algorithm (code provided) really polynomial (benchmark provided)?

This is the algorithm I'm using: http://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs/14115627#14115627 Specifically C#, but the linked thread has numerous languages. ...
2
votes
2answers
102 views

How are games like chess provably harder than NP?

From this question, I had the debate about how problems harder than NP are proved. I said that intuitively I understand it as (from this video explaining that some problems are provably harder than ...
3
votes
2answers
327 views

What complexity class would this version of generalized chess fall?

By now I understand that generalized chess is harder than NP, and is EXPTIME-complete for the decision problem "Given an nxn board with a given position, can white force a win?" because the proof ...
5
votes
1answer
85 views

Does P=NP imply polynomial solutions to #P?

Is it true that $\#P$-complete problems could possibly be solved in polynomial time if P=NP? I know that even some counting problems related to polynomial time decision problems are $\#P$-complete, so ...
5
votes
1answer
150 views

How to compute the sum of this series involving golden ratio, efficiently?

Definitions Let $\tau$ be a function on natural numbers defined as $\tau(n)=\lceil n*\phi^2\rceil$ where $n$ is some natural number and $\phi=\frac{1+\sqrt{5}}{2}$ is the golden ratio. This series ...
2
votes
1answer
63 views

Why is the set of perfect squares in P?

I am reading an article by Cook [1]. In it he writes: The set of perfect squares is in P, since Newton's method can be used to efficiently approximate square roots. I can see how to use Newton's ...
1
vote
0answers
23 views

Why do we set conditions f(n) ≥ n resp. f(n) ≥ log(n) the Time resp. Space Hierarchy?

In the Space (Time) Hierarchy Theorem and also fully space (time) constructibility of two function we have the condition: being greater than $log(n)$ (being greater than $n$). Why do we have these ...
5
votes
2answers
345 views

Is DTIME(n) = DTIME(2n) true? (unlike Rosenberg's results)

I'm reading Homer and Selman's "Computability and Complexity" book. In some Corollary 5.3 it says: For all ε‎ > 0, DTIME(O(n)) = DTIME( (1+ε‎‎) n). Now I'm confused with this corollary and ...
3
votes
6answers
788 views

Is there a meaningful difference between O(1) and O(\log n)?

A computer can only process numbers smaller than say $2^{64}$ in a single operation, so even an $O(1)$ algorithm only takes constant time if $n<2^{64}$. If I somehow had an array of $2^{1000}$ ...
0
votes
1answer
68 views

Longest path in DAG or finding DAG diameter

A directed acyclic graph (DAG), is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that there is no way ...
1
vote
1answer
53 views

Understanding hashtable performance in the worst-case

Under assumption that the hash function is uniform, we have worst-case performance for the search operation in a separate-chaining (e.g. java.util.HashMap) ...
2
votes
0answers
27 views

What is the Time Complexity of the Matrix Exponential?

While trying to compute the Matrix Exponential of an nxn array I decided to take advantage of a Python function called ...
3
votes
0answers
24 views

How to compute amortized complexity of n runs of Dijkstra's algorithm?

I'm trying to figure out how to compute an amortized complexity/ or complexity of this algorithm. We have a Graph which is oriented. And we are going to run Dijkstra's algorithm for finding a shortest ...
2
votes
1answer
76 views

Reccurrence for the game of pile of stones

I am trying to solve this question from Project Euler for past few days: Divisor game. The problem is as follows: Two players are playing a game. There are $k$ piles of stones. When it is his turn ...
0
votes
1answer
28 views

Is better than O(n^2) possible for getting pairs that sum to a multiple of 10?

Is it possible to solve a problem with a worse case less than $O(n^2)$, when the input is an an array of numbers and the output is all pairs that sum to a number divisible by 10? for example ...
2
votes
2answers
197 views

Want to know the time complexity inner for loop which is partially iterating the array

Question: Find out next increasing value of each element in this below array. int[] array = { 5, 2, 7, 10, 4, 12} e.g) 5's nextIncreasingValue: 7 2's ...
2
votes
0answers
45 views

Hamming numbers for $O(N)$ speed and $O(1)$ memory

Disclaimer: there are many questions about it, but I didn't find any with requirement of constant memory. Hamming numbers is a numbers $2^i 3^j 5^k$, where $i$, $j$, $k$ are natural numbers. Is ...
4
votes
2answers
91 views

What are some “easy” unreasonable implications of O(1) time memory access?

If you are given a memory address $n$ bits long, then you need to at least process those bits. Hence, if you have $N$ memory available, addressed by $n$ bits, it would take $O(\mathbf{log}(N)) = O(n)$...
0
votes
1answer
41 views

When the heapsort worst case occurs?

The best-, average-, and worst case time complexity of Heapsort for $n$ distinct keys are all $\Theta(n \lg n)$. What are the worst-case inputs for heapsort?
0
votes
1answer
88 views

Complexity of the Dijkstra algorithm

I'm little confused by computing a time complexity for Dijkstra algorithm. It is said that the complexity is in $O(|V|^2)$ - Wikipedia - Dijkstra, which I ...
0
votes
0answers
21 views

Why is Knuth Sequence's slower than regular ShellSort?

I have tried running it over and over again with varying input sizes. But it keeps showing Donald Knuth's sequence as slower? Why is this? I figured it would be faster. ...
1
vote
0answers
30 views

Analysis of Weighted Quick Union with Path Compression

I have searched the internet for an analysis of why WQUPC is amortized $O( m \alpha (n) ) $ for m operations on n nodes ( $\alpha ( n) $ is the inverse Ackerman function). I understand why it is $O ( ...
8
votes
3answers
304 views

Why are loops faster than recursion?

In practice I understand that any recursion can be written as a loop (and vice versa(?)) and if we measure with actual computers we find that loops are faster than recursion for the same problem. But ...