# 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.

2,405 questions
Filter by
Sorted by
Tagged with
1 vote
113 views

### What is the difference between solving and verifying an algorithm in the context of P, NP, NP-complete, NP-hard

I am struggling to understand the difference between the notions $P, NP, NP-$complete, $NP-$hard. Let's take the example of the $NP-$class. We say that these problems are solved in non-polynomial time,...
61 views

### Why the APPROX-VERTEX-COVER algorithm is O(V+E)?

In the Introduction to Algorithms Book By Thomas H. Cormen, Third Edition, they give an approximation algorithm for the Vertex Cover Problem with 2-approximation ratio: Where G is undirected graph. ...
• 59
15 views

### Finite complexity meta-algorithm to generate (non-asymptotically) polynomial time shortcuts to EXPTIME problem of arbitrary input size

I might be able to find a polynomial time reduction to an EXPTIME algorithm of finite size, but is it possible for a finite-description-length algorithm to exist that finds polytime shortcuts for any ...
• 101
1 vote
28 views

### Are there EXPTIME-complete problems which are also in IP?

I am wondering if there are known to be any EXPTIME-complete problems (or even just problems in EXPTIME) which are known to also be in IP, so a prover can convince a verifier that an answer to an ...
• 271
### Iterative solution of recurrence relation $T(n)=4T(\frac{n}{2})+\frac{n^3}{log_2n}$
Please help me to find the Time Complexity of the recurrence relation $T(n)=4T(\frac{n}{2})+\frac{n^3}{log_2n}$ using iterative method.