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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
14 views

Sum of coprime divisors

Define the following function to be the count of integers not greater than $L$ that are coprime to $n$:$$C(n,L)=\sum_{k=1 \atop {GCD(n,k)=1}}^L1$$ Then I am interested in the following sum: $$S(x)=\...
3 votes
1 answer
52 views

Counting integers $n \leq x$ with a given prime signature

Given is a prime signature $S$ and an integer $x$. The task is to count how many integers $n$ exist such that $n \leq x$, and if $n = p_1^{k_1}p_2^{k_2}p_3^{k_3}p_4^{k_4}...$ then $S = (k_1,k_2,k_3,......
1 vote
0 answers
33 views

Product of all possible ranges in a sequence

Given a sequence $a_1,\ldots,a_n$, we want to compute $$\prod_{\ell=1}^{n-1} \prod_{r=\ell+1}^n (\max(a_\ell,\ldots,a_r) - \min(a_\ell,\ldots,a_r)).$$ For example, given $1, 2, 4$, the result should ...
-1 votes
0 answers
13 views

Asymptotic Practices

I try to find Big-O, Big-Ω and Big-Θ of the following equations: 1. n + 5n^0.5 2. 3n^2 + 5n + 1 If I correctly understood the difference between them, then my ...
  • 1
1 vote
1 answer
35 views

Best known deterministic algorithm for generation of any (non random) n-bit prime?

Sometimes we need some prime number with certain minimum size for modular algorithm. For practical purposes we can precompute (using fast randomized algorithms) table of some primes for range which ...
  • 265
0 votes
1 answer
45 views

In merge sort, what will be the time complexity if in each recursion, we break the array in two parts of size 1/4 and 3/4 respectively?

Let's say number of elements are a power of 4. Now if we break the array in parts of 1/4 and 3/4, how do we calculate the time complexity in this case?
0 votes
1 answer
26 views

Improving an algorithm involving two pairs of sums

Suppose $l=[a[0],a[1],a[2],,a[n]]$ be a list of numbers. I need to calculate $$ \sum a[j]a[k]a[j']a[k'] $$ such that $j+k=j'+k'$ .Obviously we can implement it in $O(n^4)$ time complexity by the ...
1 vote
1 answer
69 views

Show that $TIME(\sqrt{n})$ = $TIME(1)$

Also known as CMU 15-455, Spring 2017, Homework 2.4. Before I ask the main questions, let me first give a sketch of my idea. First, recall the definition of big-$O$ and time complexity class $TIME(t(n)...
2 votes
1 answer
33 views

Sieve of Eratosthenes for factorization: bitwise complexity?

As is well-known (and easy to prove), carrying out a sieve of Eratosthenes on the first $N$ integers takes a number of word operations in the order of $N \sum_{p\leq \sqrt{N}} 1/p \sim N \log \log N$, ...
4 votes
1 answer
83 views

Optimal algorithmic complexity of "a nonrepetitive stack"?

I'm wondering about the optimal complexity - or at the very least, some way of achieving non-terrible complexity - of a particular stack variant, that I'm calling a 'nonrepetitive stack'. A ...
  • 1,320
0 votes
1 answer
51 views

Can an algorithm decide whether any DFA accepts an infinite language? What is its time complexity?

Given a DFA with m number of input alphabet and n number of states. What is time complexity to check DFA accepts infinite language (i.e infinite length of strings)?
  • 1
0 votes
0 answers
15 views

For a function $f \in PF$, is the $range(f) \in NP$ always?

For a function $f \in PF$, is the $range(f) \in NP$ always? It seems to me that since any function that you can verify in $P$ time is in $NP$, you can always just run the function on the input to ...
0 votes
1 answer
25 views

Is there a possibility to convert the following problem into divide and connquer

$A$ is a $m*n$ matrix $B$ is an $n*n$ matrix I want to return matrix C of size m*n such that: $C_{ij} = \sum_{k=1}^{n} max(0, a_{ij} - b_{jk}) $ In pseudocode it could be like below ...
  • 163
5 votes
3 answers
4k views

Is there a faster than O(n^2) way to compute a vector of length n from another vector and an n by n matrix?

$A$ is an array of length $n$ $B$ is an $n\times n$ matrix \ I want to return an array C of size n such that: $$C_{i} = \sum_{j=1}^{n} \max(0, a_i - b_{ij}) $$ In pseudocode it could be like ...
  • 163
1 vote
1 answer
35 views

Automatic differentiation - Upper bound time

Is there any proof or reference or intuition for the following theorem related to AAD: Any function f of n variables f(x1,...,xn) can be differentiated with respect to every variable xi at a ...
  • 109
0 votes
1 answer
15 views

Algorithm to optimise the cost to choose a subset of array

I have been on this problem for very long time, Lets assume we have a shopping list eg:{milk,bread,coke,orange,apple,..} and the shop only sells pack of thing and ...
0 votes
3 answers
74 views

Can we create a decision tree for any comparison sorting algorithm even if it is very complicated?

I am reading an algorithm book. Any comparison sort must make $\Omega(n\log(n))$ comparisons in the worst case to sort $n$ elements. Can we create a decision tree for any comparison sorting algorithm ...
0 votes
1 answer
33 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 ...
  • 135
-2 votes
0 answers
56 views

Time complexity of example algorithm

...
0 votes
1 answer
50 views

Time complexity analysis for Searching in a Hash table

I want to analyse the time complexity for Unsuccesful search using probabilistic method in a Hash table where collisions are resolved by chaining through a doubly linked list. And the doubly linked ...
0 votes
2 answers
26 views

How to find the runtime out of a recursion formula when using divide and conquer

In dived and conquer one uses the following formula to find the runtime: $$T(n) = aT(n/b) + f(n).$$ I am confused with the meaning of the constants $a,b$ as well as by the question how to find f(n). ...
0 votes
2 answers
183 views

Combining fork() and algorithms

Today in my algorithms class, my professor explained how in divide and conquer algorithms we do things in "parallel" although I felt it was not exactly in parallel. Then I remembered from OS ...
0 votes
0 answers
35 views

Can 0 be a tight upper bound of -4n?

I'm newbie in algorithm time complexity. I had a function, f(n) = 2n2 - 4n. I have to proof that f(n) = O(n2). We can take it ...
-1 votes
1 answer
21 views

what will be the time complexity of the following procedure?

...
  • 1
0 votes
1 answer
57 views

Set of Turing machines that accepts at least one input in bounded time

What is known about the languages: $$S_f = \{ [M] \ | \ \exists{x} \ \text{s.t.} \\ M \ \text{accepts} \ x \ \text{in} \ f(|[M]|) \ \text{steps}, \\ \ |x| \leq f(|[M]|) \}$$ I used to think that in ...
  • 155
0 votes
1 answer
43 views

Running time of SAT and other EXPTIME algorithms

I need to propose an algorithm for a NP-hard problem. I use dynamic programming which leads to a running time $O(2^s\cdot n^2), s\leq n.$ The algorithm aims to finding a path in a graph $G(V, E)$ (in ...
0 votes
0 answers
17 views

Time complexity of Trie autocompletion (multiple variables in time complexity)

I am trying to understand what the time complexity for an autocomplete function for a Trie-based dictionary would be. Every node contains a letter and whether it is the last letter of a word, and if ...
0 votes
2 answers
36 views

translating operations per second (OPS) to floating point operations per second (FLOPS)

I have some algorithmic complexity estimates in Giga Operations Per Second (GOPS) and I would like to compare those with the capabilities of state-of-the-art processors. However, the processor ...
3 votes
3 answers
729 views

A solution with O(n) time complexity is always slower than a solution with O(nlog(n)) time complexity even though they have the same space complexity

Why is Solution 1 faster than Solution 2? The input passed to both solutions: ...
0 votes
0 answers
14 views

How to compare two functions which themselves contain additions/subtraction between two functions?

I'm new to Asymptotic Notation and wanted to know how to compare two functions which contain sub functions or contain addition/subtraction of other functions. For example : f(n) v g(n), where f(n) = a(...
1 vote
3 answers
98 views

What is the difference between solving and verifying an algorithm in the context of P, NP, NP-complete, NP-hard

I am struggling to understand the difference between the notions $P, NP, NP-$complete, $NP-$hard. Let's take the example of the $NP-$class. We say that these problems are solved in non-polynomial time,...
-3 votes
0 answers
29 views

A time complexity question which I'm unsure about

I had that question in my university test: The answer provided is O(nlogn), however, the recurrence seems to be expressed as T(N) = 2T([N/2]) which is proved to be O(N). Am I wrong? If yes, I'd like ...
0 votes
2 answers
42 views

Why the APPROX-VERTEX-COVER algorithm is O(V+E)?

In the Introduction to Algorithms Book By Thomas H. Cormen, Third Edition, they give an approximation algorithm for the Vertex Cover Problem with 2-approximation ratio: Where G is undirected graph. ...
  • 59
0 votes
0 answers
13 views

Finite complexity meta-algorithm to generate (non-asymptotically) polynomial time shortcuts to EXPTIME problem of arbitrary input size

I might be able to find a polynomial time reduction to an EXPTIME algorithm of finite size, but is it possible for a finite-description-length algorithm to exist that finds polytime shortcuts for any ...
1 vote
0 answers
26 views

Are there EXPTIME-complete problems which are also in IP?

I am wondering if there are known to be any EXPTIME-complete problems (or even just problems in EXPTIME) which are known to also be in IP, so a prover can convince a verifier that an answer to an ...
-3 votes
2 answers
43 views

Iterative solution of recurrence relation $T(n)=4T(\frac{n}{2})+\frac{n^3}{log_2n}$

Please help me to find the Time Complexity of the recurrence relation $T(n)=4T(\frac{n}{2})+\frac{n^3}{log_2n}$ using iterative method.
  • 1
3 votes
1 answer
52 views

Proof sketch of Blum's Speedup Theorem

In his Quantum Computing Since Democritus, Scott Aaronson outlined a proof sketch of Blum's Speedup Theorem which roughly looks like the following. Given an enumeration of Turing Machines $\{M\}_{i \...
  • 31
1 vote
1 answer
35 views

Why is calling an O(n) time algorithm on each node of a tree O(nlogn) time?

Assume we have a balanced binary tree. On each node, we call: ...
0 votes
1 answer
28 views

What are some algorithms with runtimes that involve a \log{n} term with a negative exponent?

Are there any (deterministic or randomized) algorithms that run in time $\operatorname{poly}(n)\log^p{n}$ for $p < 0$? What are some examples?
  • 961
1 vote
1 answer
39 views

Time complexity for finding the number of triangles in a graph

In our class we considered the problem written in the title. The below given time complexities where simply given, but not derived or explained. Therefore I tried myself to derive them, while I using ...
  • 185
1 vote
0 answers
24 views

Time complexity of LP problems

In almost all websites and papers, the complexity of LP problem is given in the number of iterations (such as https://or.stackexchange.com/a/5924). I was wondering if there are any references where ...
0 votes
0 answers
24 views

What will be the Computational Complexity in terms of order O of the operations shown in the following figure

Suppose I have L bits. First, I want to multiply the L bits with L orthogonal codes of length N, and then I want to add all the vectors. So, first, I have to do a scalar multiplication with a vector ...
1 vote
1 answer
35 views

fastest algorithm for rectangular linear assignment problem

I want to optimally assign $m$ jobs equally to $n$ workers, where $m>n$. Assume $m = an$ for some integer $a$, so that each worker must get exactly $a$ jobs. (The rectangular linear assignment ...
  • 90
3 votes
1 answer
113 views

Find the largest segment within a queried range?

We are given $k$ segments $(s_1,e_1),(s_2,e_2),(s_3,e_4),...,(s_k,e_k)$ where $s_i\le e_i$. Now we are given a query interval $[L,R]$ to find the largest segment $(s_i,e_i)$ contained within $[L,R]$. ...
3 votes
2 answers
85 views

Rank in a Convex Combination

Given vectors $A, B \in \mathbb{R}^{n}$, $w \in [0,1]$ and $x \in \mathbb{R}$, let $$ Rank(A,B,w,x)=\sum_{i=1}^{n} \boldsymbol 1 \{w A_{i} +(1-w) B_{i} < x\} $$ denote the number of elements in the ...
0 votes
1 answer
48 views

Complexity of solving two different LP problems

I have one LP problem (LP1) to solve, where a term in a constraint is to be substituted after solving another LP problem (LP2) (with a different variable vector). Suppose I call the dimension of the ...
1 vote
1 answer
43 views

Turing machine read time

Suppose I have a Turing machine that takes as input any string of length $n$, where $n$ is odd, and the Turing machine returns the middle character of the string. What time complexity class is this in?...
1 vote
1 answer
25 views

shortest path increases monotonically => a bound on the length of one iteration of Edmons-Karp is then O(E) ... Convince me this is true

I was reading the proof of time-complexity for the Edmonds-Karp algorithm here (https://brilliant.org/wiki/edmonds-karp-algorithm/). Everything in the first part of the proof (The section ...
3 votes
1 answer
76 views

Given two strings ABC and CBA, find A, B and C

Given two strings ABC and CBA, find A, B and C. Input: abcacab, cabcaab Output: ab, ca, cab The time complexity of brute force is O(n^3). Are there any better algorithms to solve this problem? Thanks!
-2 votes
1 answer
31 views

Inversion array of a given array

Let A[1...n] be an array of n distinct numbers. The ordering of the numbers is any permutation of [1,2,...,n]. An array Inv_A is defined as follows: Inv_A[i] = number of elements A[j] such that j<i ...

1
2 3 4 5
48