# Tagged Questions

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.

26 views

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 ...
115 views

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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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}$ ...
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 ...
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) ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$...
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?
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 ...
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. ...
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 ( ...