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

### How to prove that we can study the complexity of Recurrence Relations by always giving in input a power of how many children each node creates?

Let's say we have the following Recurrence Relation: $$T(n) = \begin{cases} 1 & n=1 \\ 3T(\frac{n}{3}) + \Theta(n) & \text{otherwise} \end{cases}$$ I've been taught I can ...
1k views

### Determine if an NFA accepts infinite language in polynomial time

Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite. (Note that converting NFA to DFA is exponential time). For any DFA,...
19 views

### Finding the Optimal Palette for a Set of Images

Motivation I want to draw pictures using indexed colors. As I have limited space for colors per-palette, I want to choose palettes in an intelligent fashion, based on the pictures I want to draw. The ...
1 vote
134 views

### Can someone help me fully grasp idea and time/space complexity with this code?

My understanding is the following: Time = With the initial not state is just to check if there are no elements in the list a. This is done in O(1) time. The first ...
100 views

### An algorithm that is $O(n^{\log(n)})$

After having searched for a while, and after having read this https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities I was just wondering: is ...
1 vote
120 views

### Most scalable distributed consensus mechanism based on message complexity?

One of the most challenges in distributed consensus mechanisms is both time complexity and message complexity. For example, PBFT message complexity is O(n^2) that ...
176 views

### Time complexity of merging two lists while preserving order

I have two lists l1 and l2 of possibly unequal sizes (say, m and ...
1 vote
63 views

### Reconstructing a string from two its partitions into substrings of varying size

Given two unordered partitions of the same string over a finite alphabet into substrings, how hard is it to reconstruct the original string? If multiple solutions exist, any one will suffice. Under an ...
33 views

### Complexity of generating all subsets of size $k$ using recursion

What is the complexity of the following (Python) code, that builds the list L of all subsets of size $k$ of a given set? ...
10 views

### Computational complexity of some optimization problem? [closed]

I wonder if there are some methods I can borrow from computational complexity theory to analyze the optimization problem such as a convex optimization problem. An example of this is to find the ...
24 views

### Problems in $DTIME(n\log n)$ [closed]

Let $DTIME(t(n))$ denote the complexity class of languages solvable in time $O(t(n))$ by a deteministic Turing machine with one tape. By the result of Kobayashi, we know that $DTIME(o(n\log n))=REG$. ...
78 views

### Find the largest possible number not larger than some integer N and is the product of K consecutive primes

Source: Hanoi student competition of unknown year (Kì thi học sinh giỏi thành phố) Additional conditions: N is a positive integer in range [1, 2^64 - 1] K is a positive integer in range [3, 10] ...
53 views

### Is GNFS quasi-polynomial-time?

Wikipedia states that the time complexity of the General Number Field Sieve (GNFS) is $$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\log N)^{\frac{1}{3}}(\log \log N)^{\frac{2}{3}}\right),$$ ...
43 views

### Modified Quicksort*

given array of size n, and a function called FindPivot which returns the median with a time complexity of O(n^(1.1)). what is the worst case time complexity of quicksort using the given func to find ...
221 views

### Time complexity of a 2-heap question

The problem statement is pretty straightforward: given an array of integers and a window size, return an array of doubles of the median of each window. $arr = 1, 3, 5, 10, 6, 9, 2$ and $k = 3$ would ...
19 views

### Recurrence relation for TSP using recursion

This is a Python algorithm using recursion to solve Travelling Salesman Problem, consider $G$ a complete graph: ...
15 views

### If the polynomial hierarchy collapses to level 1, what is the significance?

Recently, I was studying polynomial hierarchy and found that many unsolved problems are related to it, such as $P=NP$,$NP=coNP$. I would like to ask, if the polynomial hierarchy collapses, what does ...
44 views

### Help with time complexity of a given code

Given the following code: ...
55 views

### How can I develop an algorithm to schedule production?

Given an an table that contains products I am selling with the dates, and given a table that contains the possible work orders with each work order, arrange the work orders such that all items are ...
1 vote
20 views

### Subquadratic multiplication of polynomials in the max-plus/tropical semiring

Is there an algorithm to multiply two polynomials with coefficients in the max-plus semiring $(\mathbb{Z}\cup\{-\infty\}, \max, +)$ which is faster than the trivial one? I'm interested in the ...
1 vote
48 views

### How much does proving that a special case of a problem is NP-complete tell me about if the general problem is NP-complete?

Define a graph problem as follows. Given a graph $G$ and two integers $c$ and $k$, delete $k$ nodes and all edges incident to them, such that, in the remaining graph, every connected component has at ...
48 views

### Why is this proof that CHESS is in EXPTIME correct?

I've been reading the following paper (open) by Fraenkel and Lichtenstein that shows that the Generalized $n \times n$ Chess problem ($\texttt{CHESS}$) is $\texttt{EXPTIME-complete}$. They start by ...
35 views

### Algorithm for detecting if H is a induced subgraph of G in O(n)

Say that I am given a graph $H$ and a graph $G$ where the maximum degree of $G$ is known. How can I use BFS to find out if $H$ is an induced subgraph of $G$ in $O(n)$ time? My current take is the ...
36 views

### Why is exponential time 2^n^k and not 2^n

Does 2^n describe a class of problems or is it considered polynomial?
68 views

### Finding the length of the longest palindrome in the given array

The problem that I'm trying to solve is: Given an array of length N, I want to find the length of the longest palindrome in the given array. With palindrome, we refer to a word, phrase, or sequence ...
57 views

### What is the time complexity of removing among $N$ sets of size at most $n$ the sets which are subsets of another set?

A naïve solution would be to first sort all sets, taking time $O(N n \log n)$. Then, for every possible pair of sets, check if one is a subset of the other, and if applicable remove the subset. This ...
45 views

### Can a program that terminates have a running time of infinity? (Or not have an upper bound)

Can we have an algorithm that takes some input and does something random to it (in such a way that the algorithm does terminate) which does not have a worst-case running time upper-bound? A (non-)...
32 views

### Are there any other language classes of time complexity between the P language class and the NP language class?

$P$ is the language class that is decidable in polynomial time by a deterministic Turing machine. $NP$ is a language class that is decidable in polynomial time by non-deterministic Turing machines and ...
49 views

### merging logn + 1 sorted subarrays

given array A of size $n$ which is made of $logn + 1$ sub arrays which are sorted, I need to sort ASAP. example of array : $A[500,501,3,8,100,1,2,9]$ as you can see, sub arrays are :$[1:2][3:5][6:]$ ...
362 views

### Is it possible to compute an equality hash for nodes in a *cyclic* directed graph in less than quadratic time?

Calculating hashes for nodes in an acyclic graph is well known using a Merkle tree. With some simplifying assumptions, a simple algorithm will also calculate hashes for nodes in a cyclic graph... but ...
1 vote
28 views

### Listing all subsets of size $k$ of $\{1,2,...,n\}$ with just $C \binom{n}{k}$ operations

I was wondering if it is possible to list all subsets of size $k$ of the set $\{1,...,n\}$ by performing at most $C \binom{n}{k}$ operations for a fixed constant $C$. I did find a way to compute these ...
92 views

### How to find average time complexity of backtracking algorithm?

Problem is to decide if it is possible to partition a given array nums into k partitions. I've written a brute force backtracking algorithm. How do we analyse this algorithm to calculate average ...
126 views

### Possibly Tractable Variation of Suguru Puzzles

I'm currently investigating the computational complexity of a modified one-dimensional Suguru puzzle. The general Suguru puzzles were recently proven to be NP-complete (see here). My investigation ...
1 vote
26 views

### number of substrings in same position with same contents

L1 and L2 are two lists which only consist of X's and Y'...
21 views

### Understanding how to assign complexity to functions

I'm having trouble understanding how to assign complexity to functions. As an example, let's take the following pseudo code of the COUNTING-SORT algorithm, taken from the book "Introduction to ...
32 views

### Algorithm Asymptotic Analysis

I'm trying to solve this time complexity: 𝑇(𝑛)=2𝑇(𝑛−2)+𝑛 but having some challenges addressing the (-2) component. Any insights on this complexity? Ended up with a section [2^2(1) + 2^(3)(2) + 2^(...
1 vote
21 views

### Can Sutner's (1991) quadratic algorithm for testing reversibility of Cellular Automata be applied to 1-D CA with even sized neighborhoods?

Admittedly I haven't fully wrapped my head around the paper yet, but I'm curious if this algorithm can be adapted to say, a one dimensional cellular automata with two states, and an even sized ...
36 views

### Design an algorithm with linear complexity

Let A[1 : n] be a vector of n integers such that all elements except O(n^2/3) elements are between 1 and 10n. Design an algorithm with linear complexity that sorts A. Beyond the algorithm, what I can'...
3k views

### To find median of $k$ sorted arrays of $n$ elements each in less than $O(nk\log k)$

How do I efficiently find the median of $k$ sorted arrays each of length $n$? Note that the total number of elements will be $nk$. I know it can be done in $O(nk \log k)$ time using merge technique. ...
1 vote
223 views

### Runtime of weighted interval scheduling dynamic programming algorithm

Consider this implementation of a dynamic programming algorithm for weighted interval scheduling: ...
44 views

### Complexity of recursive function that calls itself with it's own return value

Given the following code: int f3(int n) { if(n <= 2) return 1; f3(1 + f3(n-2)); return n - 1; } I was trying to find the time complexity and I got this ...
76 views

### Prove that $O(\sum_{i=0}^{h}{2^i\times(h-i)}) \sim O(2^h)$

I want to prove that, $$\sum_{i=0}^{h}{2^i\times(h-i)} \sim O(2^h).$$ I did come up with the below proof, $$\sum_{i=0}^{h}{2^i\times(h-i)} \sim O(\sum_{i=0}^{h-1}2^{h-1}) \sim O(h2^h),$$ but as it is ...
74 views

### How to find the standard theta notation of this?

Hi i am practising standard theta notation: How could i find the standard theta notation of the following : 2n + 3n^2(log n)^3 + 2 and ...
25 views

### Are there efficient ways to check if large numbers are prime [duplicate]

I was recently playing around in Python, and I wrote a program to check if a given number is prime. It works by checking to see if its divisible by each number other than 1 leading up to itself. It ...
1 vote
If an algorithm takes two numbers $b$ and $n$ and its input size satisfies $O(\log_2{n} + \log_2{b})$ plus its time complexity satisfies $O(b \log_{2}{n})$, what is the time complexity relative to the ...