# Questions tagged [time-complexity]

The amount of time resources (number of atomic operations or machine steps) required to solve a problem expressed in terms of input size. If your question concerns algorithm analysis, use the [runtime-analysis] tag instead. If your question concerns whether or not a computation will *ever* finish, use the [computability] tag instead. Time-complexity is perhaps the most important sub-topic of complexity theory.

187 questions
Filter by
Sorted by
Tagged with
11k views

### Can a Big-Oh time complexity contain more than one variable?

Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct ...
27k views

### A d-ary heap problem from CLRS

I got confused while solving the following problem (questions 1–3). Question A d-ary heap is like a binary heap, but(with one possible exception) non-leaf nodes have d children instead of 2 ...
1k views

### Collection of APX-hard problems

Everyone knows "Garey & Johnson", which is my go-to reference whenever I need a problem to transform from for an NP-hardness proof. However I recently find myself in need of an APX-hardness proof, ...
3k views

### Is there an algorithm whose time complexity is between polynomial time and exponential time？

We often hear about some algorithms' running time that is polynomial, and some algorithms' running time that is exponential. But is there an algorithm whose time complexity is between polynomial time ...
26k views

### Evaluating the average time complexity of a given bubblesort algorithm.

Considering this pseudo-code of a bubblesort: ...
7k views

### Longest common substring in linear time

We know that the longest common substring of two strings can be found in $\mathcal O(N^2)$ time complexity. Can a solution be found in only linear time?
8k views

### Complexity of Towers of Hanoi

I ran into the following doubts on the complexity of Towers of Hanoi, on which I would like your comments. Is it in NP? Attempted answer: Suppose Peggy (prover) solves the problem & submits it ...
1k views

### Proving that if $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$

I'd really like your help with proving the following. If $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$. Here, $\mathrm{NTime}(n^{100})$ is the class of ...
744 views

### Prove or refute: BPP(0.90,0.95) = BPP

I'd really like your help with the proving or refuting the following claim: $BPP(0.90,0.95)=BPP$. In computational complexity theory, BPP, which stands for bounded-error probabilistic polynomial time ...
2k views

### Is it possible to get Nth Fibonacci number in sublinear time?

I was researching the topic of Fibonacci numbers and asymptotic complexity of generating them. Coming across a seemingly paradoxical conclusion, I've decided to check out if you agree with my ...
579 views

### Why don't we emphasize "length of input string" when considering time complexity of sorting algorithms?

The knapsack problem is $O(c\,n)$ where $c$ is the capacity of knapsack and $n$ is the number of items. Yet it's exponential because the size of the input is $\log(c)$. However, why don't we ...
1k views

### sock matching algorithm

There are $n$ pairs of socks, all different. They all went out of the dryer, so there are now $2n$ socks scattered around. Given two socks, the only operation I can do is to decide whether they are ...
423 views

### Is the memory-runtime tradeoff an equivalent of Heisenberg's uncertainty principle?

When I work on an algorithm to solve a computing problem, I often experience that speed can be increased by using more memory, and memory usage can be decreased at the price of increased running time, ...
8k views

### Why is $\Theta$ notation suitable to insertion sort to describe its worst case running time?

The worst case running time of insertion sort is $\Theta(n^2)$, we don’t write it as $O(n^2)$. $O$-notation is used to give upper bound on function. If we use it to bound a worst case running time of ...
2k views

### Prerequisites of computational complexity theory

what's the prerequisite topics needed for understanding computational complexity theory and analysis of algorithm ...including big-O and Big-theta notations and these staff. I want a mathematical ...
1k views

### Why aren't P and P/poly trivially the same?

The definition of P is a language that can be decided by a polynomial time algorithm. The definition of P/poly can be taken to mean a language that can be decided by a polynomial-size circuit (see ...
1k views

### Why do we say that polynomial time is easy? [duplicate]

For years, I've been told (and I've been advocating) that problems which could be solved in polynomial time are "easy". But now I realize that I don't know the exact reason why this is so. ...
1k views

### Machines in P undecidable?

Given a Turing machine $M$, we say that $L(M) \in P$ if the language decided by the machine can be decided by some machine in polynomial time. We say that $M \in P$ if the machine runs in polynomial ...
99 views

### Find two numbers in array $A$ such that $|x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time

I'm struggling with the following question: Let $\langle a_0, a_1,\dots,a_n\rangle$ be a sequence of real numbers, and let $M = \max\{a_0, a_1, .... a_n\}$ and $m = \min\{a_0, a_1, .... a_n\}$....
636 views

### Why not polynomial-space reductions for $PSPACE$-hardness?

A language $L'$ is $PSPACE$-hard if for every $L \in PSPACE$ we have $L \le_p L'$. Here $L \le_p L'$ means that $L$ is polynomial-time reducible to $L'$. Why does we use time reductions instead of ...
298 views

### Minimum edge deletion partitioning

I'm interested in the time complexity of the following problem: Given an undirected graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color the ...
6k views

67 views

### What is the complexity to show this theorem?

Given a sum of regular expressions, where each regular expression in the sum is n-1 concatenations of 0, 1 and (0+1). There is need to show that the sum of all regular expressions is either equal to ...
3k views

4k views

### Can we do better than $O(n\log n)$ building a balanced binary tree?

I'm (foolishly it turns out) confident that the answer to this question is no. So why am I asking? Because Dr. Aleksandar Prokopec at EPFL in his parallel programming course introduces a data-...
793 views

### Complexity of Linear Diophantine equations

My question is simply, can linear Diophantine equations be solved in polynomial time? Specifically, I am looking at equations of the form $a_1 x_1+a_2 x_2 + ... + a_n x_n = k$, where $a_i,x_i,k$ are ...
3k views

### Can a subset of an NP-complete problem be in P?

The problem is NP-complete (proven) for all input data (without exception). We assume that P != NP. Is it possible that there is an (infinitely large) subset of the problem, for which this subset is ...
11k views

### Time complexity of set intersection

This problem involves the time-complexity of determining set intersections, and the algorithm must give output on all possible inputs (as described below). Problem 1: The input is a positive ...
775 views