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

0
votes
0answers
20 views

Time complexity of quicksort for arrays in increasing or descreasing order

Two $n$-size arays are given: $n_1$ is in decreasing order and $n_2$ is in increasing order. Let $c_1$ be the time complexity for $n_1$ using quicksort, and $c_2$ the time complexity for $n_2$ using ...
0
votes
0answers
28 views

What is the time complexity of the below algorithm?

Below I have two algorithms for finding the maximum 2 numbers from an array of numbers of size>=2. n=Size of the array Algorithm 1:- 1. Loop through the array, find the index of max number. (n ...
0
votes
1answer
25 views

Is this problem hard? Finding all the subsets of size k from a sequence of n numbers

I want to know the hardness of finding all subsets of size k from a sequence of n numbers. There is an algorithm based on recursion: Print all possible combinations of r elements in a given array of ...
0
votes
3answers
24 views

Relative efficiency of n tasks in 1 loop vs. 1 task each in n loops?

Say I have 3 simple tasks, to find the min, the max, and the average of an array of numbers. A modular approach would be to write one function for each, thus iterating over the array thrice. However, ...
2
votes
2answers
55 views

Is determining if a Turing machine runs in constant time decidable if one assumes it halts?

As the title states, is determining if a Turing machine runs in constant time decidable if one assumes it halts? The decision problem, more formally: Given a Turing machine $M$ where it is assumed ...
2
votes
3answers
376 views

Given a sorted array with n elements and element x that is inside the array at position k, find k in O(min(logk, log(n-k)))

Given a sorted array $A[1,\ldots,n]$ and element $x$ that located at position $k$. We know $x$, we don't know $k$. Write an algorithm that finds $k$, in $O(\min(\log k, \log(n-k))$ time complexity. ...
2
votes
2answers
83 views

Decidability of equivalence to existential formulas

I'm looking for an algorithm to recognise if a given first order formula over a fixed vocabulary admits a logically equivalent existential one (i.e. a formula in prenex form where all quantifiers are ...
0
votes
1answer
48 views

Design an algorithm that solves the same problem in. O(nlogn) time. Prove it’s time complexity [on hold]

I have the following algorithm and need to solve the problem in a more efficient O(nlogn) time. ...
5
votes
2answers
457 views

Logic behind O(n) solution for 'Maximum length sub-array having given sum'

I am unable to understand the logic behind O(n) solution of this classical problem- Maximum length sub-array having given sum (...
1
vote
1answer
36 views

Asymptotic relation between n! and (n+1)!

I am having difficulty writing this formally. I know that by L'Hospital's rule we can reduce it to $\lim_{n \to \infty} \frac{n+1}{n}$ which is a constant and hence $n = \theta (n+1)!$. But I am not ...
0
votes
1answer
21 views

Polynomial multiplication coefficients

I was wondering about the following interesting questions: Polynomial multiplication can be done in $O(nlog(n))$ using FFT where n is the degree of the polynomial. What about finding a specific ...
1
vote
1answer
110 views

Sorting lower bounds for almost sorted array

Can't find a good way to tackle the problem. Would appreciate any help. $A$ is an $n$ items array from an ordered set, in which every item is at most $\log n $ indices away from its position in the ...
2
votes
1answer
43 views

Time complexity to find Median of Medians

I recently wrote my Grad school Admission test few days back and the following question appeared in the test. There are 'n' unsorted Arrays : A1, A2, ...., An. Assume that 'n' is odd. Each of A1, A2, ....
1
vote
2answers
46 views

Pseudo Code optimization

Summary: I am struggling with the Pseudo code for an that algorithm assigns "least filled slot first" to a tasks on multi-core chip. Detail So far I have written following: What I do not like ...
1
vote
1answer
33 views

Heap operating in time $\Gamma^{-1}(n)^2$

I have a priority queue implementation which I claim has the following worst case asymptotic run-times for the given operations: PEEK_MIN …………………………… O(1) POP_MIN…………………………… O( (INVERSE_Γ(n)) ^2). ...
3
votes
3answers
88 views

Complexity of forming a min heap out of a given array with k inversions

If a given heap has $k$ inversions, what is the complexity of making it into a valid min heap? We could define an inversion as a tuple (node, descendant), where the node has a key value strictly ...
0
votes
0answers
27 views

Is NP $\cap$ co-NP $\subsetneq$ NEXP $\cap$ co-NEXP?

The Nondeterministic Time Hierarchy Theorem implies that NP $\subsetneq$ NEXP. And the same can presumably be said about co-NP. But what about the intersection NP $\cap$ co-NP?
1
vote
1answer
13 views

Poly-time reductions for proving EXPTIME-hardness are _not_ enough?

Wikipedia says that in order to prove EXPTIME-hardness of our problem, we need to prove that every EXPTIME problem can be poly-time reduced to our problem. Here is a "counter-example" that bugs me. ...
1
vote
2answers
49 views

Running Time of Sorting Algorithm

Determine the asymptotic running time of the sorting algorithm maxSort. Algorithm maxSort(A) Input: An integer array A Output: Array A sorted in non-decreasing order ...
1
vote
1answer
32 views

Computing number of ways to make change

Given a list $C=[c_1,c_2,\dots,c_k]$ of positive integers, representing the values of $k$ varieties of coins, and a positive integer $n$, let $f(n,C)$ be the number of handfuls of coins with total ...
1
vote
1answer
18 views

Binary Tree Multithreaded Time Complexity

Let's say you want to get the value of all nodes in a binary tree (order doesn't really matter). If in each thread, you spawn two more threads to deal with the left subtree and the right subtree, then ...
0
votes
0answers
36 views

The computational cost of the adjacency-based Euclidean distance matrix

I know that the computational cost of the adjacency matrix is n*n. Namely, this graph-theoretical structure contains value 0 or 1 for every pair of vertices if there the edge exists or not, so it ...
7
votes
4answers
104 views

What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?

We have a function which takes an array as input. It breaks an array into $\log_2(n)$ parts with equal sizes where $n$ is the size of the subarray. It keeps breaking each of the subarrays until there ...
1
vote
1answer
55 views

Running Time for Finding Maximum

Consider the algorithm findMax that finds the maximum entry in an integer array. Algorithm findMax($A$) Input: An integer array $A$ Output: The maximum entry of $A$ ...
0
votes
2answers
45 views

How to calculate time complexity of a randomized search algorithm?

Example: Finding an element from a sorted array Let's say we have an algorithm that accepts a sorted array of length N as its input. Then in each iteration it randomly selects an element from the ...
3
votes
0answers
65 views

Polynomial time algorithms for rank 1 elliptic curves over Q

As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way to calculate a ...
2
votes
2answers
33 views

Check if K-Sum Variation is NP-Complete

Problem Given a range of integers $\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such that the sum is equal to $s$. Question This problem came from evaluating some scheduling algorithms that I am ...
1
vote
1answer
53 views

Worst-case complexity in terms of n?

I have this algorithm taken out from the Manual of Algorithms Analysis: ...
1
vote
1answer
34 views

How to write recurrence relation for backtracking problem?

I am not able to understand how to write a recurrence relation for n queen problem. I searched on web and everywhere it was given directly without explaining how can we arrive to that. Recurrence ...
1
vote
0answers
30 views

How can an arbitrary Turing machine running for $t$ steps be simulated in $O(n \log(n))$ steps?

I'm confused about a point regarding the Time Hierarchy Theorem. In order to establish the upper bound for this theorem it's necessary to show the following: We're given $(\langle M \rangle, t)$ ...
-2
votes
0answers
33 views

Number of distinct traingle vertices

I was given the following question to solve: Consider you are given N distinct points with both a positive x coordinate and positive y coordinate. For each coordinate you are to form a right ...
3
votes
2answers
68 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 a smaller upper ...
2
votes
0answers
34 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) ...
5
votes
2answers
99 views

Return copy of array, each element product of all others, constant additional space, no division

Question: I am trying to solve question 6.10.1 from Elements of Programming Interviews. The task is as follows: Given an array $<a_1, \ldots, a_n>$ of fixed-...
0
votes
1answer
45 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
34 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
49 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
31 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
26 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
2answers
51 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'...
1
vote
2answers
33 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
10 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
26 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
52 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
16 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 ...