# Questions tagged [time-complexity]

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

294 questions
Filter by
Sorted by
Tagged with
2k views

### Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$

I've never seen an algorithm with a log in the denominator before, and I'm wondering if there are any actually useful algorithms with this form? I understand lots of things that might cause a log ...
455 views

### What is the complexity of model checking Process Logic (LTL fragment)?

Process Logic is a modal logic allowing to reason about temporal properties of programs. Its formulae take the form similar to (Propositional) Dynamic Logic $[P]\phi$, with $P$ being a program (think ...
124 views

### Real-time countable vs fully time-constructible

Real-time countable functions were used in time hierarchy theorem in the papers of Hartmanis and Stearns (Theorem 9, 9.1 ...) and also of Hennie and Stearns (Theorems 3, 5, 7 ...). Now it is a "...
775 views

### Equivalent definitions of time constructibility

We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes at most $f(n)$ ...
55 views

### Algorithmically compute a reasonable bound on the runtime of an algorithm [duplicate]

Possible Duplicate: Are runtime bounds in P decidable? (answer: no) Originally asked on SO: https://stackoverflow.com/questions/13371025 I have seen many questions asking if this computation is ...
128 views

### Computational Complexity of RESTRICTED primality testing

Input: Any number $n \in \mathbb{Z}^+$ that can be represented in the form of $n = 2^a + b,\ |b|= c$. output: YES if $n$ is prime , else NO . Now, length of binary input is $\log(a) + O(1)$ which ...
433 views

### Optimal NP solvers

Fix $X \subset \lbrace 0,1 \rbrace^* \times \lbrace 0,1 \rbrace^*$ an NP-complete search problem e.g. the search form of SAT. Levin search provides an algorithm $L$ for solving $X$ which is optimal in ...
3k views

### What is computational complexity of calculating the Variance-Covariance Matrix?

I am using a calculation of the Variance-Covariance matrix in a program I wrote (for Principal Component Analysis), and am wondering what the complexity of it is. While obviously the Eigenvector ...
154 views

### Speed-up of universal computation by caching

A universal computer is a program that can execute any other program. It is interesting to ask whether there are "booster" computers that execute programs faster than they execute "on their own". In ...
2k views

### Near-Sort quicksort algorithm faster than O(nlgn) [closed]

Here, we define a nearly-sorted array with k-sized error, as this: Elements in the array may be in the wrong order, but only if they are not distanced by more than k indices. For example: 1, 2, 3, 6, ...
2k views

1k views

272 views

### How many steps does this recurrence take to get to 2 (or 1)?

$T(2) = T(1) = 1$ $T(n) = T(\frac{n}{\log n}) + \Theta(1)$ Basically, I wanted to know how many steps before the recursion stops? I tried various approaches, but am not getting anywhere. I know for ...
1k views

### Are there decidable problems for which for no algorithm we can give time bounds?

Are there decidable problems such that for no algorithm which solves the problem we can give a time bound as a function of the length n of the input instance? I arrived at this question because I was ...
639 views

### Different definitions of complexity

I'm a math student and have encountered the concept of (mainly time) complexity of algorithms in several courses so far (Analysis of Algorithms, Cryptography, Numerical Analysis). However what strikes ...
348 views

### Solving multiple instances of 3SUM generated from the same set

(this is a follow-up of my previous question, which uses the 3SUM' problem instead of 3SUM) Suppose we have a list $S$ of $n$ integers. Usually, for 3SUM, we only determine if there exist $a$,$b$,$c$ ...
Is anything known about the complexity of the following problem beyond membership in PTIME: Given a finite Markov chain $M$, an initial state $q_0$ and a set $F$ of (absorbing) states, is the ...
For an undirected graph $G$ and a given set $S$ of vertices, what is the asymptotically fastest known algorithm for finding a simple path containing all elements of $S$. What if we require the path to ...