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

Filter by
Sorted by
Tagged with
1
vote
1answer
8 views

Summation of asymptotic notation

How can we solve summation of asymptotic notations like given below: Summation (BigO(n)) over k for 0 < k < n.
0
votes
0answers
5 views

time complexity turing machine equal to “n + 1”

I have not clear why the time complexity is n+1 and not n+2. Consider a TM with a single tape and alphabet {0,1} and the string | * | 0 | 1 | 1 | 0 | 1 | 0 | * | ...
4
votes
2answers
486 views

Are there any proofs of exponnential lower bound time complexity

I'm trying to understand what are the techniques to prove an exponential time lower bound. For some problems, we can prove that the size of the output is exponential is the size of the input, thus it ...
1
vote
5answers
40 views

Why is finding the closest pair of points by brute force search O(n^2)?

If I have n points A, B, C, D it seems like finding the closest pair via brute force search would go like: Compare A to every item (n-1) Compare B to every item (...
0
votes
1answer
21 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,...
1
vote
1answer
33 views

Time Complexity: Big-O

What is the time complexity of this loop? k=1 for(j=0;j<=n;j+=k) k++; Is it $O(n)$ as we are increasing $j$ linearly?
2
votes
1answer
25 views

Conditions under which the 3-partition problem is not strongly NP-complete?

I'm a bit confused about the 3-partition problem. More specifically I'm confused about this from the Wikipedia article: Let B denote the (desired) sum of each subset Si, or equivalently, let the ...
1
vote
1answer
45 views

Finding minimum in PRAM model

Show that the minimum of $n$ elements stored in an array can be found in a time in $O(\log(n))$ using $O(n/\log(n))$ processors assuming an EREW-PRAM machine is given.
0
votes
1answer
24 views

Upper bound for runtime complexity of LOOP programs

Recently I learned about LOOP programs, which always terminate and have the same computational power as primitive recursive functions. Furthermore primitve recursive functions can (as far as I ...
2
votes
0answers
90 views
+100

Time Complexity for Nearest Neighbor Searches in kd-trees

Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof. In order to calculate the average number of ...
0
votes
0answers
26 views

sequence of insert and delete operation in (2,3)-tree

I need help by understanding a theorem and its proof from a script. It says "There is a sequence of $n$ insert and delete operations in a (2,3)-tree that require $\Omega ($n log n$)$ many split and ...
1
vote
1answer
21 views

Special case of the $MST-$ Problem

I am working on the following exercise: Consider an undirected complete graph $G(V,E)$ and positive real numbers $a_1,a_2,\ldots,a_n$. The task is to find a MST with respect to the edge weights $...
2
votes
1answer
81 views

Can we solve this problem more efficiently than trying all possible combinations

Here is the context of the problem I am struggling with. I have a set of strings, for example: ...
1
vote
0answers
36 views

Find minimum pair number based on selection algorithm

If we have n balls in a red box (each ball is assigned a different number from 1 to n) and n balls in a green box (again each ball is assigned a different number from 1 to n). Lets say we have a ...
-2
votes
2answers
70 views

Show that: $0.01n \log n - 2000n+6 = O(n \log n)$

Show that $0.01n \log n - 2000n+6 = O(n \log n)$. Starting from the definition: $O(g(n))=\{f:\mathbb{N}^* \to \mathbb{R}^*_{+} | \exists c \in \mathbb{R}^*_{+}, n_0\in\mathbb{N}^* s. t. f(n) \leq cg(...
0
votes
0answers
23 views

Check the Complexity time of Power method

Hi i have write a function in Matlab to calculate the power method and i wont to find the time complexity. ...
3
votes
0answers
20 views

Complexity of finding an alternating Hamiltonian (x,y)-path in edge bicolored complete graphs

Let $G$ be a simple complete graph with an edge-2-coloring. An alternating Hamilton (x,y)-path is a Hamiltonian path which starts at vertex $x$ and ends at vertex $y$ such that the colors of its ...
0
votes
0answers
30 views

MaxClique is DP-hard

I want to show that MAX−CLIQUE={(G,k)|the largest clique of G is of size exactly k} is DP-complete The idea is reduce MAX-CLIQUE to C={(G1,k1,G2,k2) | G1 has a k1-clique and G2 does not ...
1
vote
2answers
115 views

Solving $T(n) = T(n/2) + T (n/3) + n $ with recurrence tree

I am trying to solve the following recurrence relation: $$T(n) = T(n/2) + T (n/3) + n $$ $$T(1) = Θ(1) $$ I guess that the time complexity is $T(n)=Θ(n)$ since $\frac{n}{2} + \frac{n}{3} < n$ I ...
3
votes
1answer
36 views

Complexity of Hamilton path in directed complete bipartite graphs

Finding a Hamiltonian path in a directed bipartite graph is NP-complete. Problem 1 What is the complexity of the problem if we insist that the underlying graph of the digraph be complete ...
1
vote
1answer
41 views

What is the time complexity of this nested loop code?

In this loop $j$ is dependent on $i$, and $j$ is executing like $n/2$, $n/2-1$, $n/2-2$, ... So does this sum up to $O(n\log n)$?
12
votes
2answers
2k views

What is the most efficient algorithm to compute polynomial coefficients from its roots?

Given $n$ roots, $x_1, x_2, \dotsc, x_n$, the corresponding monic polynomial is $y = (x-x_1)(x-x_2)\dotsm(x-x_n) = \prod_{i}^n (x - x_i)$. To get the coefficients (i.e. $y = \sum_{i}^n a_i x^i$), a ...
0
votes
1answer
52 views

Time Complexity of the below code? [duplicate]

here is a nested loop where all the variable are integers.This is another question to the thread. I understood the solution part , but stuck in the time-complexity part. What is the time complexity ...
1
vote
2answers
50 views

Dividing 2 integers with some constraints

This a problem i came across while practicing binary search. Here is the problem: Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. ...
1
vote
1answer
26 views

Worst Case running time of the Minimum Vertex Cover Approximation algorithm

Considering this factor $2$ minimum vertex cover approximation algorithm : Repeat while there is an edge: Arbitrarily pick an uncovered edge $e=(u,v)$ and add $u$ and $v$ to the solution. ...
1
vote
3answers
53 views

How to mathematically prove that a relation T(n)=T($\sqrt{n}$)+c is O(log(log(n))?

following question, I understood the intuition behind how cutting down the size of input by square root on each iteration leads to O(log(log(n))) complexity. I tried to derive it on paper. Let T(n) =...
0
votes
1answer
123 views

Minimum descending stacks

Assume a randomly ruffled pack of n cards with numbers from 1 to n. Each time we pick the top card from the pack (while there are still cards) and we put them according to the following rules: The ...
3
votes
2answers
59 views

Why is the lower bound for sorting strings Ω(d + nlogn)?

I'm taking an Advanced Algorithms course. I'm currently studying efficient algorithms for sorting strings. In this chapter, it is provided a lower bound for the time complexity of $\Omega(d + n\log{n})...
1
vote
0answers
32 views

How Expensive is Projecting onto a Polytope?

I have a problem where our action set is a polytope $\mathcal P\subset \mathbb R^d$ and an algorithm that involves projecting onto the action set. For example it says to select the Euclidean ...
3
votes
1answer
49 views

Linear sorting algorithm

I'm trying to understand sorting algorithms. And I'm thinking about a totally different way to tackle sorting: Use array indexes to sort a given set of integers. Suppose We want to sort a list of ...
1
vote
0answers
28 views

Is there any general, theoretical limit to time - space tradeoff?

In many algorithms, one can spot that improvements in time often are occupied by more memory requirements. For example usage of cache allows to speed up calculations by saving results in memory. Is ...
1
vote
1answer
30 views

Computing order statistics $1,2,4,8,\ldots,n$

On an array of $n = 2^k$ numbers, where $k$ is a non-negative integer, the $k = \log n$ order statistics $1, 2, 4, 8,\ldots, 2^k$ can all be determined in a total of $Θ(n)$ time in the worst case. I ...
0
votes
0answers
12 views

Detailed explanation of Perlin Noise algorithmic complexity

I am doing a project in analysis of algorithm and I have been looking all over for something more complex than Perlin Noise is $O(n \cdot 2^n)$ because of the doubling in $n$ dimensions and array ...
4
votes
3answers
145 views

Finding the hidden treasure

Let's assume I am trying to find a hidden treasure. The treasure is hidden at an uknown position x. We know that the position x of the treasure is somewhere on the integer axis (in other words x is ...
0
votes
1answer
48 views

Complexity of finding 7th smallest element in a min-heap? [duplicate]

I don't know if it's allowed to traverse nodes in a min-heap. Because, if traversal is allowed then for finding $7^{th}$ smallest element, only a constant number of nodes need to be checked, thus ...
1
vote
1answer
40 views

Time complexity described by recurrence relation

I need to find the time complexity described by the following recurrence relation. $T(n) = T(n/2) + T(n/3) + T(n/6) + n$ $T(1) = \Theta(1)$ The solution must be something like $T(n) = \Theta(f(n))$....
5
votes
4answers
124 views

How do you find a hash function that respects a custom equality function?

I've been tasked with hashing arbitrary types in C++, with the caveat that A == B implies hash(A) == hash(B) even if equality of ...
1
vote
1answer
30 views

Time complexity of recursive function

I am trying to find out how they calculated the time complexity of this small function . I am studying for an exam and found this question and the final answer is given, but I am trying to understand ...
1
vote
0answers
16 views

Construct neighbourhood relation graph for n sequences

Given $n$ sequences with length $m$, $s_i=\langle c_1^ic_2^i\dots c_m^i\rangle, i = 1,\dots, n$, where $c^i_j\in D$ is a partial ordered set and the partial order relation $\sqsubseteq$ on $D$ answers ...
0
votes
1answer
27 views

Question about growth rates of functions involving n and logn

I was studying for an algorithm exam and was having trouble answering (or rather proving) one of the practice problems. I want to find the correct symbol among $o$, $\omega$, $\Theta$ that would best ...
0
votes
0answers
29 views

time complexity of 2 sum problem using binary search

this is a popular searching problem and the question is : Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The ...
0
votes
0answers
20 views

Dynamic programming solution to Matrix chain multplication order - time complexity

I am unable to understand why the dynamic programming solution to Matrix chain multiplication order problem is O(n^3). Can someone please help understand the reasoning? To me, it looks like the ...
2
votes
0answers
18 views

Poset data structure to find least element, greater or equal to given

Let $A$ be a finite set, and $S \subset \mathcal{P}(A)$. Is there a data structure for $S$ that would allow to quickly retrieve an element $q \in S $, given a key $p \in \mathcal{P}(A)$, such that $q$ ...
2
votes
1answer
67 views

How is the max of two random variables has O(n^2) time-complexity?

Suppose we have two discrete random variables and we want perform maximum operation to obtain the max PDF. We know that max of two independent random variables is: if $Z = max(X,Y)$ $pr(Z = k) = pr(...
2
votes
1answer
37 views

Are chaotic systems computable in polynomial time

Suppose the parameters/inputs of the computation include the time at which the configuration of a particular deterministic chaotic system needs to be computed. Say, for instance, as input we have a ...
0
votes
0answers
21 views

Highest safe rung problem?

Highest Safe rung problem : There are many rungs on a ladder in increasing order of height. A bottle is thrown from a rung, and depending on the height of the rung, the bottle may break or may not (...
1
vote
1answer
39 views

Do problems that have unary encodings automatically become unary languages?

This problem has confused me a lot, can any of you help me out. Thank you.
0
votes
1answer
39 views

Why does this triple loop code have a running time of 1.5lnN * N^2

Hi all, I'm currently going through the Princeton Algorithms course on coursera, and I'm having trouble understanding the answer to this quiz. I think I understand where the $\frac{1}{2} N^2$ term ...
2
votes
1answer
52 views

Practical hard 3-sat instances

The $3-SAT$ problem is known to be NP-complete problem. Which means that (as far as I understand), unless $P \neq NP$, for every algorithm $A$ which decides $3-SAT$, $A$ runs in super polynomial time (...
2
votes
1answer
29 views

number of comparisons in searching algorithms

i was going thorugh different searching algorithms,Linear,binary and ternary search.Now i want to know the number of comparisons in these. For linear search : ...