Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 [tag:runtime-analysis] instead. If your question concerns whether or not a computation will *ever* finish, use [tag:computability] instead. Time-complexity is perhaps the most important sub-topic of [tag:complexity-theory].

2
votes
0answers
23 views

Complexity of multiplying two integers of size $n$ and $m$

The multiplication of two integers of size $n$ can be done in time $O(n \cdot \log n \cdot \log\log n)$ using FFT method. If the two integers have different sizes $n$ and $m$, does an upper bound ...
0
votes
0answers
20 views

Complexity of generating non-uniform random variates

What can we say about the complexity of generating (negative) binomial and (negative) hypergeometric random variates? In particular, it is possible to generate (negative) binomial and (negative) ...
2
votes
0answers
39 views

Update each element to product of all others in linear time, constant additional space, no division

Question: I am trying to solve question 6.10.1 from Elements of Programming Interviews. I have only been able to find an $O(nlog(n))$ time and $O(log(n))$ ...
0
votes
1answer
30 views

Is TSP a more detailed form of the “Set Inclusion” question?

Set Inclusion GIVEN: set of cards, some with blue backs, and each with a positive, integer face value. QUESTION: Are there any [blue-backed cards] with a [face value <= L]? 2 independent ...
2
votes
2answers
29 views

Are Big-Theta functions asymptotic monotonically non decreasing?

For example, suppose $f(n) = \Theta(n^2)$, then does that mean for any sufficiently large $n$, $f(n) \le f(n+1)$? Is it a general case for all Big-Theta?
1
vote
1answer
27 views

What's the worst case complexity of Robert W. Floyd's cycle detection algorithm?

Givens. I understand Floyd's algorithm can determine the length $\lambda$ of the loop and the length $m$ of the tail. The hare will not necessarily catch the tortoise on the first cycle, but it is ...
0
votes
1answer
27 views

Why is a heap better than a linked list for implementation of a priority queue?

Using a heap, you have O(log(n)) insertion and O(log(n)) removal. Using a linked list, you have O(n) insertion and O(1) removal. Why is it better to have log-n for both than n for one and constant ...
0
votes
0answers
25 views

What is the ideal complexity of a task with (n-1)!/2^(n-1) possible threes?

I have n elements to connect. Each element has a given length. My objective is to connect all the elements, so that I get one large, with length sum of all elements. The elements must be connected the ...
1
vote
1answer
15 views

Multi-variate complexity semplification

I developed an algorithm with the following multi-variate complexity: $$O((k^n+kn)l^{kn}),$$ where $n,k,l$ are variables. I have very little knowledge of complexity theory, and I'm not sure whether ...
0
votes
0answers
22 views

N-Queens problem - maximum number of function calls

N-Queens problem - maximum number of function calls. We say, that a backtracking algorithm (code below) 'checks' a setup of N queens, when the function isFree(n-1, y) is called for $0\leq y < n$ ...
1
vote
1answer
32 views

How does quicksort with 3-way partitioning ~ $(2 ln 2) NH$ become linear time complexity with many duplicated keys?

From Algorithms 4th: Quicksort with 3-way partitioning uses ~$(2\ln 2)NH$ compares to sort $N$ items, where $H$ is the Shannon entropy, defined from the frequencies of key values. $ H = -(p_{1}\...
0
votes
1answer
35 views

Quick and space-efficient way to find whether two sets intersect

I hope you can help me - Given a lot of sets containing integers, I'd like for any two sets, to quickly (i.e. O(1)) ask whether they intersect. Note that I don'...
0
votes
2answers
28 views

Does NTIME($n^\alpha$) $\subset$ EXPTIME imply NP $\subset$ EXPTIME?

I think I'm able to prove NTIME($n^\alpha$) $\subset$ EXPTIME for arbitrary $\alpha$. Is this a new result? If it was, would there be a way to deduce NP $\subset$ EXPTIME from it?
0
votes
0answers
9 views

definition of speedup for Amdahl's law

Say I have an algorithm C running in time T that decomposes into two "subalgorithms" A and B that run in time p*T and (1-p)T so that algorithm C takes time pT+(1-p)*T. Say I have another algorithm C' ...
0
votes
1answer
23 views

Point rank in 2D plane time complexity?

I'm reading about the algorithm of finding the ranks of all points in a 2D plane, I don't understand the time complexity formula for it. It has four steps: Compute the median of x-coordinates of all ...
0
votes
2answers
50 views

How do you detect if an algorithm is running at O(nlogn)?

Given only input and output(e.g. runtime), how do you know if an algorithm is running at O(nlogn) time complexity? For example, how does LeetCode detect my code is running at O(nlogn)? https://...
0
votes
1answer
22 views

Why $xx^TM$ requires $O(dk)$ operations?

Suppose $x \in \mathbb{R}^d$ and $M \in \mathbb{R}^{d \times k}$. Why $xx^TM$ requires $O(dk)$ operations?
1
vote
0answers
14 views

Is there a space-filling curve with constant-time indexing?

The Hilbert curve and other space-filling curves I've read about seem to have mapping operations from 1-D index to N-dimensional coordinates that are efficient, but amount to a ...
1
vote
1answer
43 views

Proving correctness of inefficient algorithm - Path between two vertices

Consider the following inefficient algorithm that decides if there is a path between two vertices s and t of a directed graph G. Show that the algorithm is correct. In addition, analyze its complexity ...
0
votes
1answer
12 views

How fast can we optimally cluster 1-D data?

K-means clustering is the problem of partitioning a set of points in a metric space into $k$ sets (clusters), such that the sum of squared distances between each point and the center of its cluster) ...
0
votes
0answers
27 views

Practical computation time, counting spanning trees and selecting spanning trees uniformly at random

I am doing a project in applied math, which involves counting spanning trees and selecting spanning trees uniformly at random for near-maximal planar graphs with ~430 vertices, as part of a larger ...
2
votes
3answers
331 views

Why aren't primality tests easily linear in time complexity?

Why don't we consider them as linear? I don't understand. You just have to check for factorization up to sqrt of n. So it's even faster than linear. I assume it's not linear only if we compare the ...
0
votes
1answer
22 views

Binary search in log time on a Turing Machine

I was thinking about TM (Turing Machine) as a computation model, and I came up with the following question : Is it possible to make a TM that answers binary search (tell wether $x$ belong to a sorted ...
2
votes
1answer
26 views

Complexity classes: What if different algorithms exist for different sizes of input?

If I understand(*) correctly, a decision problem is some function $f(x)$ whose function argument $x$ can be represented by data of a limited length (e.g. not an irrational number) and whose value is ...
5
votes
1answer
56 views

Least number of guesses needed to determine all unknown subsets of a set

Say I have a set $\mathbb{S}=\{1,2,...,n\}$. I have an adversary who breaks up $\mathbb{S}$ into $k$ unknown and disjoint subsets. Denote this new set $\mathbb{A}$. I can guess any combination $s$ and ...
1
vote
2answers
68 views

Show that for any real constants $a$ and $b$, where $b > 0$, $(n + a)^b = \Theta(n^b)$

I'm currently studying growth of function chapter in Introduction to Algorithm. In exercise 3.1-2 the question is: Show that for any real constants $a$ and $b$, where $b>0$, $(n + a)^b = \...
0
votes
0answers
12 views

Deciding complexity class of a TM s.t M(0) = accept

Below is a sample of 2 homework TM where Im not sure what complexity class they fit in. Also have to decide the complexity class of the complement. These 2 in particular confuse me because I got a ...
-1
votes
0answers
36 views

How to find the maximum difference between n numbers efficiently?

Suppose there are n employees and I need to find the difference between maximum and minimum salaries of these n people. What would be the most efficient way to do that? Will $O(n)$ time work?
0
votes
2answers
56 views

Time Complexity and graphs

I'm learning graphs these days and need to clear few doubts- Can I determine weather 5 points in two dimensions whose X and Y coordinates are given lie on the same straight line in O(1). What is the ...
1
vote
1answer
24 views

Determine whether a system of $n$ linear equations has solutions in $\{0, 1\}^n$ in polynomial time

I'm trying to determine whether it is possible to decide if a system of $n$ linear equations with integer coefficients and $n$ variables has a solution in $\{0, 1\}^n$ in polynomial time. ...
1
vote
0answers
21 views

How to maintain completely dynamic convex hull quickly?

If there's no deletion, we can use $2$ balanced trees to maintain $2$ half convex hulls(up and down). In this way, we can insert $n$ points in $O(n\log n)$ time.(In the beginning, there are no points) ...
2
votes
1answer
36 views

Compute the general time complexity of a merge sort algorithm with specified complexity of the merge process

The problem was from an exam, I spent much time wrapping my head up around this kind of problems, so I decided to ask for help ;( Problem: We implement a merge sort algorithm to sort $n$ items. The ...
1
vote
1answer
29 views

What is the meaning of max() in intro. to algorithms?

I'm reading chapter 3(growth functions) of CLRS and in giving an example of proving theta for a standard quadratic function the book gives the following value for $n_0 = 2 \cdot max(|b|/a, \sqrt{|c|/a}...
0
votes
1answer
54 views

Minimum finger search tree complexity

Suppose I have an AVL tree with a pointer to the minimal element. I'd like to conduct a search for some key x, which is the $k$-smallest key in the entire tree. I can do this by "climbing" up the tree'...
6
votes
2answers
127 views

Can a list with $\mathcal{O}(1)$ access have an insertion complexity better than $\mathcal{O}(n)$?

It seems intuitive that there's no list data structure which has $\mathcal{O}(1)$ worst case time complexity for random access and a worst case complexity better than $\mathcal{O}(n)$ for insertion: ...
0
votes
1answer
37 views

How can I create zero-collision-free strings more efficiently?

$S$ is a symmetric set If $|S|=3$ such that $S=\{n_1, n_2, n_3\}$ then $n_1+n_2 = n_3$, If $|S|=4$ such that $S=\{n_1, n_2, n_3, n_4\}$ then $n_1+n_3=n_4$ and $2n_2=n_4$, If $|S|=5$ such that $S=\{...
1
vote
1answer
46 views

Getting N top scores from a matrix

I start with a matrix, lets say 4x4. So I want the N top scores, with the sum of one element of each row. For example: ...
0
votes
1answer
28 views

Showing that algorithm has STOP property and finding its computational complexity function

The task is to show that given algorithm has STOP property and to find its computational complexity function. $\alpha:$ $n \ge 0$ ...
3
votes
1answer
81 views

Find all values repeating more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time

Given a parameter $k$ and an array (not sorted) of length $n$ return all values which repeat more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time. I've managed this in $O(nk)$ time, but can't ...
4
votes
2answers
52 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\} $....
5
votes
3answers
122 views

Can we remove duplicates faster than we can sort?

The problem is (integer) duplicate removal, which can also be perceived as producing the image of an evaluated function (of integers): Given a sequence $S_\text{in}$ of $n$ integers, produce a ...
0
votes
1answer
16 views

Forming polylines from a list of individual lines

I want to optimize a SVG path made entirely of lines. Given a list of lines, each made of two 2D points connected together, I want to find an equivalent list of polylines. For example: ...
1
vote
3answers
84 views

Is this algorithm of constant time?

I have the following code in Python: ...
0
votes
2answers
54 views

How can I solve the recurrence $f(n) = 3f(\frac{n}{4}) + \log(n)$?

The master theorem didn't work here. I tried to do the substitution method but I ended up with an additional term: $2Σ(i \cdot 3^i)$. Also I should find the solution $g(n)$ such as $f=\Theta(g)$.
1
vote
1answer
60 views

Proving that co-finite languages can be decided in constant time

I am trying to show that given a co-finite language $A$, $A \in \text{TIME}(1)$. If $A$ is co-finite, $A$ is regular, so $A \in \text{TIME}(n)$. I'm not sure how to proceed from here. Any hints?
3
votes
2answers
104 views

Efficiently shuffling items in $N$ buckets using $O(N)$ space

I’ve run into a challenging algorithm puzzle while trying to generate a large amount of test data. The problem is as follows: We have $N$ buckets, $B_1$ through $B_N$. Each bucket $B_i$ maps to a ...
1
vote
1answer
34 views

Find Hamiltonian cycle in polynomial time

I want to know for what types of graph it is possible to find Hamiltonian cycle in polynomial time. It would be helpful also to show why on some types of graph finding Hamiltonian cycle would be only ...
0
votes
1answer
31 views

How to compare an element with other elements within an array efficiently for a condition

I need to compare each index with one another and associated array value as well. For example, ...
3
votes
0answers
15 views

Power of 2 assumption in Divide and conquer [duplicate]

Currently doing an Algorithms course in my 2nd year of university (I am a maths student, but thankfully at Warwick University, we have quite a flexible degree). One of the topics we cover is the ...
1
vote
1answer
27 views

How to calculate $\sum_{i=1}^n \mu^2(i)$ in less than $O(n)$'s time

To go with $O(n)$, we can use the linear sieve according to that $\mu(n)$ is multiplicative. But it seems that we don't have to work each $\mu(n)$ out and accumulate them together, because I only want ...