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
0
votes
1answer
27 views

Difference between a skiplist and an Indexable skiplist

Can someone please help me understand the main differences between a simple skiplist and an indexable skiplist? How does an indexable skiplist work in comparison to a normal skiplist (maybe a little ...
0
votes
0answers
16 views

CNF2 = { φ | φ is a satisfiable CNF-formula in which each variable appears at most 2 times}. Show CNF2 is in P

CNF2 = { φ | φ is a satisfiable CNF-formula in which each variable appears at most 2 times}. Show CNF2 is in P. I found this solution: We use the method of resolution to take the variables out ...
1
vote
1answer
32 views

Upper (or lower) envelope of some linear functions

Given some single variable linear functions $y_1=m_1x+b_1$, $y_2=m_2x+b_2$, $\ldots$, $y_n=m_nx+b_n$, the upper envelope is the function $f(x)= \max \{y_1, \ldots, y_n\}$. We know that this function ...
0
votes
0answers
48 views

Does this algorithm sort in worst-case time-complexity $\mathcal O (n)$?

It has always buggered me that sorting in $\mathcal O (n)$ is not possible and I've been thinking about it from time to time. So, I've had an idea but am not really sure if it really can sort in $\...
5
votes
1answer
512 views

Assuming P != NP, what is the cardinality of the set of NP-Hard languages?

If P=NP, then every non-trivial language is NP-Hard, so clearly there are uncountably many NP-Hard languages. However it's less clear to me what the cardinality of this set is assuming P != NP.
0
votes
0answers
12 views

Time Complexity calculation using recursion tree method

What is the time complexity of the following recurrence equation : T(n) = T(n/2) + T(n/4) + T(n/8) + n I solved it using recursion tree method and I'm getting O(n) as the answer. Please let me know ...
0
votes
1answer
25 views

Analysis of Pan-cake sorting

i was implementing pan-cake sorting. We can implement it by taking largest element to start and flipping it recursively (Like selection sort). However it is mentioned that the A[i] has to be a ...
1
vote
2answers
44 views

Time complexity to sort 100 elements by using selection sort?

What will be time complexity for sorting 100 elements using selection sort answer given is O(1), but selection sort time complexity is O(n^2) in every case so how O(1)?
3
votes
2answers
111 views

Time Complexity: Why does $n^n$ grow faster than $n!$?

Seeing the title, you will probably like to give your explanation as $n!=n\times (n-1)\times (n-2)\times (n-3)\times\cdots\times 1$ where as $n^n$ = $n\times n \times n\times n \times\cdots\times ...
26
votes
4answers
6k views

Which Grows Faster: Factorial or Double Exponentiation

Which of the functions among $2^{3^n}$ or $n!$ grows faster? I know that $n^n$ grows faster than $n!$ and $n!$ grows faster than $c^n$ where $c$ is a constant, but what is it in my case?
0
votes
0answers
30 views

Find a non-minimal sequence of elements covering the support set

Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in O(1) time with arbitrary positions). Denote $\text{...
0
votes
0answers
9 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 | * | ...
5
votes
2answers
545 views

Are there any proofs of exponential 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 ...
0
votes
5answers
67 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
41 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
38 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
30 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
46 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
34 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 ...
5
votes
0answers
122 views

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
29 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
25 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
82 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
43 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
73 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
26 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
33 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
119 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
44 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
31 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
57 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
129 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
61 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
33 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
53 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
13 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
150 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
53 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
41 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
127 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
31 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
2answers
42 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 ...