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

### Finding big O notation of function with two parameters

I'm looking to work out the big-O notation for the following: $$\frac{n^{s + 1} - 1}{n - 1} - 1$$ I have a feeling the result is $O\left( n^s \right)$ but I'm not sure how to prove it. Any help ...
126 views

### determine if a machine prints a certain string in less time than it takes to run the machine itself?

Does there exist a procedure that determines if a polytime machine prints a certain string, and does so in less time than the machine itself takes to run? Define a machine $a$ that analyzes another ...
185 views

### Time - Complexity Convex Optimization and Eigen Decomposition

Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be? Is the ...
632 views

### Asymptotic time complexity of a two-loop program

I have two pieces of code in a function which I'm trying to calculate the asymptotic running time for: ...
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 ...
6k views

### What is the relationship between NP/NP-Complete/NP-Hard to time complexity?

I'm familiar with a few problems of each class and even though the definitions are based on sets and polynomial reducibility, I see a pattern with time complexity. NP problems appear to be $O(2^n)$ (...
9k views

### Is there a O(log n) algorithm for matrix exponentiation?

Is there an algorithm to raise a matrix to the $n$th power in $O(\log n)$ time? I have been searching online, but have been unsuccessful thus far.
1k views

### Clarifications on polynomial reducibility for problems in P and NP-complete

Can I always increase the complexity of a problem via polynomial reduction? (in which case 'reduction' is really a misnomer) For example, if I have a classic P problem (say, finding the smallest ...
2k views

### complexity of decision problems vs computing functions [closed]

This is an area that admittedly I've always found subtle about CS and occasionally trips me up, and clearly others. recently on tcs.se a user asked an apparently innocuous question about N-Queens ...
142 views

### What constitutes one operation/cycle/move in the RAM model?

I saw a RAM model diagram that displayed an input tape, output tape, the program (read-only), the instruction pointer, and the memory registers. However, when I look at questions of time complexity, ...
304 views

### Complexity inversely propotional to $n$

Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?
4k views

### Does Quicksort always have quadratic runtime if you choose a maximum element as pivot?

If you have a quick-sort algorithm, and you always select the smallest (or largest) element as your pivot; am I right in assuming that if you provide an already sorted data set, you will always get ...
208 views

### Complexity calculations, assumptions on basic costs [duplicate]

Possible Duplicate: How can we assume comparison, addition, … between numbers is $O(1)$ When we calculate the time-complexity of some algorithm we make many simplifications (or assumptions)...
19k views

### Time complexity of a triple-nested loop

Please consider the following triple-nested loop: ...
1k views

### How to write a recursive function that with certain time complexity

I'm now doing exam revision, and from some past year exam papers, I noticed some questions that ask to write a recursive method with signature like ...
354 views

### What is the complexity of this subset merge algorithm?

Updated Algorithm: There was a major flaw in my original presentation of the algorithm which could have impacted the results. I apologize for the same. The correction has been posted underneath. The ...
409 views

### Why larger input sizes imply harder instances?

Below, assume we're working with an infinite-tape Turing machine. When explaining the notion of time complexity to someone, and why it is measured relative to the input size of an instance, I ...
95 views

### Run time of product of polynomially bounded numbers

Let $M$ denote a set of $n$ positive integers, each less than $n^c$. What is the runtime of computing $\prod_{m \in M} m$ with a deterministic Turing machine?
898 views

### Running time of CDCL compared to DPLL

What's the complexity of Conflict-Driven Clause Learning SAT solvers, compared to DPLL solvers? Was it proven that CDCL is faster in general? Are there instances of SAT that are hard for CDCL but easy ...
153 views

### Problem with the definition of P

In "Introduction to Algorithms: 3rd Edition" there is Theorem 34.2, which states $P = \{ L \mid L \text{ is accepted by a polynomial-time algorithm} \}$ "Accepted in polynomial-time" is defined by:...
4k views

### How fast can we find all Four-Square combinations that sum to N?

A question was asked at Stack Overflow (here): Given an integer $N$, print out all possible combinations of integer values of $A,B,C$ and $D$ which solve the equation $A^2+B^2+C^2+D^2 = N$. This ...
278 views

### Why does NTIME consider the length of the longest computation?

In Sipser's textbook "Introduction to the Theory of Computation, Second Edition," he defines nondeterministic time complexity as follows: Let $N$ be a nondeterministic Turing machine that is a ...
107 views

### distinction between $\textbf{P}^{\# \textbf{P}}$ and $\# \textbf{P}$-Complete

We know that $\# \textbf{P}$ is closed under polynomial sums, i.e., sum of polynomially many $\# \textbf{P}$ functions is still in $\# \textbf{P}$. Functions in $\textbf{P}^{\# \textbf{P}}$ are those ...
9k views

### Most efficient known priority queue for inserts

In terms of asymptotic space and time complexity, what is the most efficient priority-queue? Specifically I am looking for priority queues which minimize the complexity of inserts, it's ok if deletes ...
1k views

### Lock-free, constant update-time concurrent tree data-structures?

I've been reading a bit of the literature lately, and have found some rather interesting data-structures. I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
10k views

### How hard is finding the discrete logarithm?

The discrete logarithm is the same as finding $b$ in $a^b=c \bmod N$, given $a$, $c$, and $N$. I wonder what complexity groups (e.g. for classical and quantum computers) this is in, and what ...
520 views

### Using hash tables instead of lists for buckets in hash tables

Say instead of using a linked list as buckets for a hash table of size $m$, we use another hash table of size $p$ as buckets this time. What would be the average case for this problem? I looked up ...
1k views

### What is the average search complexity of perfect hashing?

The lookup time in perfect hash-tables is $O(1)$ in the worst case. Does that simply mean that the average should be $\leq O(1)$?
3k views

### What's the complexity of Spearman's rank correlation coefficient computation?

I've been studying the Spearman's rank correlation coefficient $\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}}$. for two ...
712 views

### Finding at least two paths of same length in a directed graph

Suppose we have a directed graph $G=(V,E)$ and two nodes $A$ and $B$. I would like to know if there are already algorithms for calculating the following decision problem: Are there at least two ...
3k views

### What is the time complexity of this function?

This is an example in my lecture notes. Is this function with time complexity $O(n \log n)$?. Because the worst case is the funtion goes into else branch, and 2 ...
511 views

### Time-space tradeoff for missing element problem

Here is a well-known problem. Given an array $A[1\dots n]$ of positive integers, output the smallest positive integer not in the array. The problem can be solved in $O(n)$ space and time: read the ...
205 views

### Semi-decidable problems with linear bound

Take a semi-decidable problem and an algorithm that finds the positive answer in finite time. The run-time of the algorithm, restricted to inputs with a positive answer, cannot be bounded by a ...
3k views

### Brute force Delaunay triangulation algorithm complexity

In the book "Computational Geometry: Algorithms and Applications" by Mark de Berg et al., there is a very simple brute force algorithm for computing Delaunay triangulations. The algorithm ...
272 views

### Attempt to write a function with cubed log runtime complexity $O(\log^3 n)$

I'm learning Data Structures and Algorithms now, I have a practical question that asked to write a function with O(log3n), which means log(n)*log(n)*log(n). ...
967 views

### Has anyone found polynomial algorithm on Hamiltonian cycle isomorphism?

As the title says, has anyone found a polynomial time algorithm for checking whether two graphs having a Hamiltonian cycle are isomorphic? Is this problem NP-complete?
272 views

### Can joins be parallelized?

Suppose we want to join two relations on a predicate. Is this in NC? I realize that a proof of it not being in NC would amount to a proof that $P\not=NC$, so I'd accept evidence of it being an open ...
111 views

### Complexity class that properly included in DLOGTIME

Is there any decision problem that is in a complexity class properly included in DLOGTIME? (except $O(1)$, of course) If there is, can we create complete problems for DLOGTIME? So, can there be ...
5k views

### Data structure with search, insert and delete in amortised time $O(1)$?

Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time? GetElement(k): Return the $k$th element of the list. InsertAfter(x,y): Insert ...
94k views

### Find median of unsorted array in $O(n)$ time

To find the median of an unsorted array, we can make a min-heap in $O(n\log n)$ time for $n$ elements, and then we can extract one by one $n/2$ elements to get the median. But this approach would take ...
654 views

### How many strings are close to a given set of strings?

This question has been prompted by Efficient data structures for building a fast spell checker. Given two strings $u,v$, we say they are $k$-close if their Damerau–Levenshtein distance¹ is small, i.e. ...
3k views

### Hashing using search trees instead of lists

I am struggling with hashing and binary search tree material. And I read that instead of using lists for storing entries with the same hash values, it is also possible to use binary search trees. And ...
149 views

### Connection between castability and convexity

I am wondering if there are any connection between convex polygon and castable object? What can we say about castability of the object if we know that the object is convex polygon and vice versa. Let'...
19k views

### How can we assume that basic operations on numbers take constant time?

Normally in algorithms we do not care about comparison, addition, or subtraction of numbers -- we assume they run in time $O(1)$. For example, we assume this when we say that comparison-based sorting ...
479 views

### Restricted version of the Clique problem?

Consider the following version of the Clique problem where the input is of size $n$ and we're asked to find a clique of size $k$. The restriction is that the decision procedure cannot change the input ...
7k views

### Complexity of finding the largest $m$ numbers in an array of size $n$

What follows is my algorithm for doing this in what I believe to be $O(n)$ time, and my proof for that. My professor disagrees that it runs in $O(n)$ and instead thinks that it runs in $\Omega(n^2)$ ...
8k views

### Complexity of computing matrix powers

I am interested in calculating the $n$'th power of a $n\times n$ matrix $A$. Suppose we have an algorithm for matrix multiplication which runs in $\mathcal{O}(M(n))$ time. Then, one can easily ...
724 views

### Finding a 5-Pointed Star in polynomial time

I want to establish that this is part of my homework for a course I am currently taking. I am looking for some assistance in proceeding, NOT AN ANSWER. This is the question in question: A 5-...
I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity. I thought about some modification on Tarjan's algorithm for ...