People who code: we want your input. Take the Survey

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
2answers
15 views

Time Complexity of Logarithmic For loop

Say I have a for loop like this ...
1
vote
1answer
20 views

Time complexity of the triangle factoring problem

We define the triangle factoring problem as in Triangle Factors in Random Graphs, which is, given a simple undirected graph of $3n$ nodes, find if there's a subset of edges dividing vertices into $n$ ...
0
votes
0answers
27 views

Find the magic value from an array of N numbers

I was asked this problem recently in an interview however, I failed to provide an optimal solution to it. Given an array $A$ of $n$ numbers, the magic factor of $i^{th}$ element is equal to the ...
0
votes
1answer
53 views

Find non common numbers in two arrays

Given two arrays of integers, please write a function that returns all elements present in one of the two arrays but not both. E.g. f([ 1, 3, 5 ], [ 1, 2, 4, 5 ]) -> [ 2, 3, 4 ] I know I can do ...
2
votes
1answer
45 views

Must all NP-complete problems have an asymptotically optimal algorithm?

According to Blum's speedup theorem, there exist problems with no asymptotically optimal algorithm. Suppose that NP-complete problems had speedup. We know a problem X with asymptotically time ...
0
votes
3answers
32 views

Can the worst-case analysis of $f(n)$ be $\Omega(g(n))$ but not $O(g(n))$?

I am struggling to wrap my head around using $\Omega$-notation to describe worst-case running time of an algorithm, or $O$-notation to describe the best-case running time. Specifically, I struggle to ...
1
vote
1answer
31 views

Map two arrays given a map of possible mappings

Given two integer arrays a and b and a map m which for each element ...
1
vote
1answer
39 views

Splay Tree, repeatedly searching for the same key that´s not in the Tree

In a Splay Tree, doing $m$ sequential search operations for the same key that is in the tree has a time complexity in $O(n+m)$ where n is the number of nodes in the Tree. Since the first search has a ...
0
votes
0answers
22 views

Tangled cable - divide and conquer

Tangled cable: Let's have a long cable, from both ends of which protrudes n wires. Each wire at the left end is connected to just one at the other end and we want to find out which one. To do this, we ...
1
vote
1answer
55 views

Time complexity of a power

I am trying to work out the time complexity of my function but I'm not sure how it works with powers. I've got $y=(\frac{x}{3})^n$ as one of my lines. How many basic operations is this? Would it be $2(...
0
votes
1answer
38 views

Changing binary counter structure such that increament and decreament methods will work in O(1) amortized

Just trying to solve the second part of a question with two parts. First part was to prove that you can't add decrement method to a standart binary counter without hurting the amortized complexity and ...
0
votes
2answers
33 views

How to get the expected time complexity of while loop?

How to get the expected time complexity of while loop below? ...
3
votes
0answers
53 views

How to replace the max distance of a bounded set of points with a random point in less than $O(n^2)$?

Context Let's say I have a finite set of points of size $N$. I can represent the points in a metric space and then compute distances between them. My goal is to replace a point in the set with another ...
12
votes
3answers
2k views

How can I quickly judge whether matrix A is the inverse matrix of B?

How can I quickly judge whether matrix A is the inverse matrix of B? This is an exercise for the course I take. This question is given in the section of randomized algorithms. So I think its solution ...
0
votes
1answer
58 views

How to solve $T(n)=4T(\sqrt{n}/3)+(\log n)^2$ with the master theorem?

Can somebody help me with this recurrence please? $T(n)=4T(\sqrt{n}/3)+(\log n)^2$
0
votes
1answer
49 views

Average time complexity of linear search

It is usually assumed that the average time complexity of the linear search, i.e., deciding whether an item $i$ is present in an unordered list $L$ of length $n$ is $O(n)$ (linear). I have read ...
3
votes
1answer
37 views

Is there a way to study precisely the complexity with respect to the size of vertex set for some graph problem?

Suppose there is graph problem $L$ such that the instance $x$ of $L$ is a simple graph with $n$ vertices and $m$ edges. In the Turing machine model, we can encode a graph using $O(n^2)$ cells or $O((m+...
0
votes
1answer
21 views

For a balanced binary search tree what is the worst case case time complexity for accessing all elements within a range of nodes?

I have this question which is asking for the worst case time complexity for a balanced binary search tree, assume the nodes are labeled as integers and we consider a range of ...
1
vote
2answers
45 views

Silly question: what counts as a “unit of work” when computing big-Oh time complexity

I am going through a fairly non-rigorous textbook called 'Cracking the code interview' and I am bothered by this terminology called "unit of work". It says in the textbook that certain ...
1
vote
1answer
24 views

Solving a problem with instance of size $n$ in $O(n)$

Today I read the following text in CLRS: We say that an algorithm solves a concrete problem in time $O(T(n))$ if, when it is provided a problem instance $i$ of length $n = |i|$, the algorithm can ...
1
vote
1answer
32 views

Algorithm for computing the sum of symmetric sums (better than $\mathcal{O}(2^N)$ )

Let denote $\mathbf{x} = \{x_1,x_2,...,x_N \}$ with $x_i \in \Bbb R$ for $i=1,...,N$ and $f(\mathbf{x},n)$ be the $n$-th symmetric sum of the set $\mathbf{x}$ $$ f(\mathbf{x},n) = \sum_{\sigma_1,...,\...
1
vote
1answer
21 views

Application of floors and ceilings to the time complexity of loop with constant index increment

Consider the number of times that 'statement' runs in the following examples. I am confused as to the applications of floors and ceilings when calculating the loop complexity. ...
2
votes
0answers
38 views

Median of given range of elements in a binary search tree

Given a range [l, r], we are supposed to find the median of all the nodes that are present in the binary search tree and whose values are within l and r. Let me take an example. Let the BST be the ...
1
vote
1answer
19 views

Possible partitions, for k-means problem(k=2)

I have this brute-force algorithm to solve the problem: Generate all possible partitions of P into two subsets of P1 and P2 For each partition P1, P2 generated in Step 1, compute the cost of the ...
3
votes
0answers
49 views

Make Change in Linear Time

The question is motivated by this post on StackOverflow. Given an integer $n$ and a finite list of distinct positive integers $ds$, let $f(n, ds)$ denote the number of ways $n$ can be expressed as a ...
0
votes
0answers
15 views

Time complexity of calculating the eigenvalues and eigenvector of a matrix

I know the time complexity of calculating the determinant of a square matrix of order $n$ is $O(n^3)$ (by using standard matrix multiplication). What is the time complexity of calculating the ...
0
votes
2answers
63 views

Find distinict elements in an array in $O(n)$ time

Given this pseudo-code that finds the number of distinct elements in the given array: ...
2
votes
2answers
43 views

Why can't one use the Cook-Levin theorem to show that TQBF is PSPACE-complete?

I have been reading Michael Sipser's Introduction to the Theory of Computation, and I have stumbled upon a paragraph in Chapter 8 (Theorem 8.9 on page 339 of the 3rd international edition) that I ...
1
vote
1answer
42 views

Is $\frac{n}{\log n} \log \frac{n}{\log n} = O(n)$?

I have an algorithm with this time complexity: $$ T(n) = O(n) + \frac{n}{\log n} \cdot \log \frac{n}{\log n}. $$ I tried to figure out how to solve this and I tried to say something like this : if I ...
0
votes
1answer
26 views

Which could be a possible time complexity?

I have the following algorithmen (picture) which calculates a Vertex Cover and gets an undirected $G(V,E)$ Graph as input. The following task is to find the possible Time complexity (estimate) while $...
1
vote
1answer
33 views

Existence of a function between two functions $f$ and $g$ where $f \in o(g)$

Is this statement true? For each two functions $f$ and $g$, where $f \in o(g)$, there exists a function $h$ where $f \in o(h)$ and $h \in o(g)$ Please note that I am using small $o$ notation.
0
votes
1answer
19 views

Finding which strings in a set of strings have a certain prefix - can it be smaller than O(number of strings*length of prefix)

If I have a set of words and need to return which of them start with a certain prefix, can that complexity be less than O(n*d), where n is the number of words and d is the prefix. I'm asking because ...
1
vote
1answer
38 views

Time complexity of checking whether a string exists in a HashSet

From what I know hash sets generally have complexity of $O(1)$ (unless the hash function is bad, but let's just ignore that for this question). However, sets need to either read the full data so as to ...
1
vote
0answers
20 views

Time complexity of system of linear equations when distribution of variables are known

I have system of linear equations over binary field $GF(2)$. Suppose there are $n$ equations with $n$ variables and equations are linearly independent. Then we can solve using Gaussian elimination ...
1
vote
2answers
74 views

Is there any algorithm that finds the time complexity of another algorithm provided that it halts?

Let us suppose that we have some algorithm A that halts for all valid inputs, can we prove the existence of another algorithm B that takes A as input and calculates the time complexity of A. Are there ...
1
vote
0answers
20 views

Language of all words of the form $ww$ is in $\mathsf{NTIME}(n)$

Show that the language $\{ ww \mid w \in \{0,1\}^* \}$ is in $\mathsf{NTIME}(n)$. I have a doubt first of all how can I prove that. Secondly, what does NTIME mean? Can we use a $k$-Tape Turing ...
1
vote
1answer
31 views

Checking the existence of a pattern in a given prefix

I need to design an algorithm that given a string $T$ of length $n$, performs $O(n)$ preprocessing, and can then answer queries of the sort "does a string $P$ of length $m$ appear in $T$ before ...
-1
votes
1answer
41 views

Time complexity of repeating a procedure $k$ times

Suppose I want to deploy the algorithm for finding connected components in a graph $k$ many times. Now the time complexity for finding connected components in an undirected graph is $O(v+e)$. Then ...
1
vote
1answer
61 views

sort array with some of the elements in a known range

Let $A$ be an array of n elements. We know that $n - \lfloor \sqrt n \rfloor$ elements are integers in range $\sqrt n$ to $n\sqrt n$ (the other $\lfloor \sqrt n \rfloor$ elements may or may not be in ...
4
votes
4answers
3k views

Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time?

I know this could be a strange question. But was there any algorithm ever found to compute an NP-problem, whether it be hard or complete, in polynomial time. I know this dabbles into the "does P=...
1
vote
1answer
41 views

Show that $(\log(n))^\alpha = O(n^\beta)$

I am trying to show that $\forall \beta \gt0, \log(n^\alpha) = O(n^\beta)$, however I cannot use the limit definition, as demonstrated in similar questions on the forum. First I show that $\log(n^\...
1
vote
1answer
50 views

Complexity of All-SAT

All-SAT is the problem of enumerating all satisfying assignments of a boolean formula. All-SAT is different from #SAT, where it suffices to find the number of satisfying assignments without ...
0
votes
2answers
24 views

Is it possible to prove that this algorithm is big Omega $n^2logn$ time complexity?

Considering the following recursive algorithm: $ T(n)= T(\frac{n}{2})+c_1(\frac {n}{2})^2+c_2n$. I was able to prove that this algorithm is $O(n^2 logn)$ I was trying to understand whether it is a ...
0
votes
0answers
76 views

How to prove that the lower bound of the Huffman coding problem is $\Omega(n \log n)$?

how to prove that the lower bound of the Huffman coding problem is $\Omega(n \log n)$? Here Huffman coding problem is Huffman encoding. For example, ...
0
votes
1answer
101 views

Color coding to get an FPT algoirthm for k disjoint triangles

The k-disjoint triangles problem is as follows: Input: A graph $G=(V,E)$ and an integer $k\in \mathbb{N}$ Output: Are there $k$ vertex-disjoint triangles in $G$? An FPT algorithm is presented here (...
0
votes
1answer
33 views

What is the time complexity of a linear search performed using 2 pointers?

For an array, I'm using a left pointer (pointing to 0) and a right pointer (pointing to end). For every iteration, if my search element is not found, I increment left and decrement right. This ...
1
vote
1answer
16 views

Induction on recursive formula

Okay so I have this recursive formula $T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)+O\left(n\right)+2*O\left(1\right) \ \ \ ➜ \ \ \ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\...
1
vote
3answers
94 views

Find if two numbers are linked by a greatest common divisor

Two numbers $x,y$ are 'connected' if $gcd(x,y)>g$. Here $gcd$ is the greatest common divisor. A path exists between two numbers $x,y$ if given $g$ and $n$ there is a sequence of numbers that ...
17
votes
4answers
4k views

Is the following problem NP-hard? (or have you seen it before?)

I genuinely don't know if the following problem is NP-hard. I have never seen it mentioned online, but it's hard to even search for exact problems like this. I have been trying to find an efficient ...
1
vote
1answer
30 views

Algorithm for finding strongest connection for a user on social network

I am working on Problem 6-1 from MIT's Fall 2011 6.006 course. The problem reads as: Problem 6-1. [30 points] I Can Haz Moar Frendz? Alyssa P. Hacker is interning at RenBook (人书 / 人書 in Chinese), a ...

1
2 3 4 5
41