# 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,080 questions
Filter by
Sorted by
Tagged with
218 views

### Finding asymptotic time complexity

So I'm studying for a midterm and my professor put out a sample exam with the answers, and I'm stuck on one of the questions. The answer is Big-O(n^2 log n) Could ...
189 views

### Deriving the exact number of execution times

So I'm studying for my data structures midterm and my professor gave out a sample midterm with the answers, but I'm having a hard time understanding one of the questions. Here's a screen cap: The ...
189 views

### Using a proof-of-work system to discourage piracy or encourage donations

Background A proof-of-work system allows one peer to prove to another peer that a certain amount of computational effort was performed. In a network setting this can be used to throttle peer requests ...
44k views

### Complexity of recursive Fibonacci algorithm

Using the following recursive Fibonacci algorithm: def fib(n): if n==0: return 0 elif n==1 return 1 return (fib(n-1)+fib(n-2)) If I input ...
2k views

### Complexity of a recursive bignum multiplication algorithm

We have started learning about analysis of recursive algorithms and I got the gist of it. However there are some questions, like the one I'm going to post, that confuse me a little. The exercise ...
82 views

### How to calculate Complexity Time O()? [duplicate]

Can anybody give me a way that i can use to calculate Complexity Time problems, i mean a way that will work on any complex code whatever it was. I can solve basic problems, but whenever the problem ...
2k views

### NTIME(f) subset of DSPACE(f)

As the question states, how do we prove that $\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n))$? Can anyone point me to a proof or outline it here? Thanks!
1k views

### Do functions with slower growth than inverse Ackermann appear in runtime bounds?

Some complicated algorithms (union-find) have the nearly-constant inverse Ackermann function that appears in the asymptotic time complexity, and are worst-case time optimal if the nearly constant ...
894 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 ...
434 views

### Finding asymptotically tight bounds $\Theta$ of two procedures

I would like to check time complexity of two procedures for which I am not totally convinced that I got it right. Now the first procedure is this: ...
664 views

### Is the DPLL algorithm complexity in terms of # of clauses or # of variables?

I'm a bit confused how worst case complexity is estimated for the DPLL algorithm. Is it in terms of number of clauses, number of variables, or something else?
106 views

### Calculate the number of elements after multiplying/adding two polynomials

Suppose I have two polynomials $f(x)$ and $g(x)$ and I somehow represent their coefficients. I have a couple of ways to hold a polynomial depending on how many significant coefficients the polynomial ...
2k views

### Can you do an in-place reversal of a string on a vanilla turing machine in time $o(n^2)$?

By a vanilla Turing machine, I mean a Turing machine with one tape (no special input or output tapes). The problem is as follows: the tape is initially empty, other than a string of $n$ $1$s and $0$s ...
204 views

### Worst-case time algorithm?...which one is faster?

Imagine that an algorithm A runs in worst-case time $f(n)$ and that algorithm B runs in worst-case time $g(n)$. Answer either yes, no, or can’t tell and could you explain me why? Is A more faster ...
707 views

### Time complexity of finding the largest factor of a number (using a specific oracle)

My question is related to this question posted on math.SE: Given an odd number, what is the quickest (constant-time) algorithm for finding its largest factor and suppose you can call a helper ...
409 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, ...
537 views

### Does the time complexity of a problem change with encoding of the problem?

Suppose I have a decision problem $D$ and I encode it to a language $L \subset \{0,1\}^*$. Now, I can also encode it to a different language $L'$. Is there any theorem relating the time complexity of ...
74k views

### What exactly is polynomial time? [duplicate]

I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not exponential....
1k views

### What linked list data structure adjustments would give me fast random lookup?

I am presently using an doubly linked list (C++ std::list) to hold a bunch of records that each have a unique integer identifier. The linked list is created in ...
14k views

### What does a polynomial time reduction mean?

I am having a little trouble understanding what is meant by a poly-time reduction. Suppose I have two algorithms $A$ and $B$ and then I say that $A$ is reducible to $B$. Does polytime reduction mean ...
276 views

### Computing 3SUM problem in $O(n\lg n) + \frac{n^2}{4}$ time

I've constructed an algorithm that solves the 3SUM problem in $O(n\lg n) + \frac{n^2}{4}$ time. I'm new to algorithms and was wondering how good is my running time? Googling didn't help. thanks..
10k views

1k views

### Quantum computers, parallel computing and exponential time

I've read that quantum computers can solve 'certain problems' exponentially better than classical computers. As I think I understand it, it's NOT the same to say that quantum computers take any ...
557 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 ...
34 views

### Is this problem in P: Finding a common key for a collection of systems of equations?

Let $B=\{b_1=g_1,\cdots,b_n=g_n\}$ be a set of binary variables $b_i$ and their corresponding values $g_i \in \{0,1\}$. Let $M=\{\sum_{e \in A}e \;:\; A \subset B\}$, i.e., $M$ is the set of all ...
513 views

### Time complexity of mutually recursive functions

Suppose I have two mutually recursive functions like this: ...
4k views

### What's better for an algorithm complexity, O(log n) or amortized O(log n)?

Some context: I'm to write a program that sorts the lines of a file in C for Linux. Since I have to read all lines of the file (fgets() for example) I'm thinking ...
964 views

### Behavior of different multiplied and added time complexities

Θ - Tightly bound O - Upper bound Ω - Lower bound I understand that for addition, the max asymptotic value is taken, for example... if ƒ1(n) = O(n) and ƒ2(n) = O(n log n), then ƒ1 + ƒ2 = O(max(ƒ1, ...
109 views

### Is the following langauge in $P$ or $NPC$

Assuming $P \neq NP$ Is the following langauge in $P$ or $NPC$: $L=\{\langle\phi\rangle\mid\phi$ is a 3CNF formula with an assignment satisfying at least half of the clauses$\}$ The first thing I ...
267 views

### Are runtime bounds decidable for anything nontrivial?

Problem  Given a Turing machine $M$ which has known runtime ${O}(g(n))$ with respect to input length $n$, is the runtime of $M \in {O}(f(n))$? Is the above problem decidable for some ...
92 views

### Complexity of a hash tables with balanced trees in the buckets

If I use a balanced tree instead of lists in a hash table implementation, and also after initializing my table I don't enlarge nor reduce the size of the table, what would be the worst case complexity?...
1k views

### Does reachability belong to P?

Reachability is defined as follows: a digraph $G = (V, E)$ and two vertices $v,w \in V$. Is there a directed path from $v$ to $w$ in $G$? Is it possible to write a polynomial time algorithm for it? ...
74 views

### Complexity of $Ax\geq 0$

May be it's a stupid question (sorry if it's the case). What is the complexity the decision problem: Input: $A\in\mathcal{M}_{n,m}(\mathbb{Z})$ does there exists $x\in\mathbb{N}^n,x>0$ such that ...
162 views

### Overlap Maximization problem

Here's the problem: I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$. Denote $c_i$ as the i-th $X$ in $c$. Informally, I want to map all the sets in ...
1k views

### Lower-bound complexities for finding common elements between two unsorted arrays

I'm facing some problems that deal with finding common elements between unsorted arrays and I'd like to know whether there are well-known lower-bounds for the worst-case and, eventually, what are ...
558 views

### Modeling the problem of finding all stable sets of an argumentation framework as SAT

As a continuation of my previous question i will try to explain my problem and how i am trying to convert my algorithm to a problem that can be expressed in a CNF form. Problem: Find all stable sets ...
5k views

5k views

### Time complexity in Big O notation for Harmonic series with first k terms missing

Firstly, let's suppose there exists an algorithm where $i$ iterates from $1$ to $n$, spending $\frac{n^2}{i}$ time in each iteration. Thanks to the well known $O(\log n)$ upper bound for the Harmonic ...
1k views

### A Problem on Time Complexity of Algorithms

For every integer $t$, is there a problem whose solutions can be verified in $O(n^{s})$ time but cannot be found in $O(n^{st})$ time? By verifying, I mean that given a candidate solution $y$, we can ...
133 views

### Why don't we scale the cost of memory access when analyzing runtime of algorithms?

Runtime for many programming languages is typically analyzed either assuming each operation takes a constant amount of time, or assuming each operation takes a logarithmic amount of time in the size ...
170 views

### Complexity of finding a subset of vertices within distance k of each other, given a set of vertices

I am trying to understand an algorithm presented in Using Stable Communities for Maximizing Modularity by S. Srinivasan and S. Bhowmick, along with its complexity results. (The complete algorithm is ...
673 views

### Algorithm analysis question in growth of functions

How would I solve the following. An algorithm that is $O(n^2)$ takes 10 seconds to execute on a particular computer when n=100, how long would you expect to take it when n=500? Can anyone help me ...