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
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+...
1
vote
1answer
29 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
50 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
25 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
34 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
39 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
20 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
50 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
16 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
66 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
57 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
2answers
83 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
28 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
54 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
28 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
75 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
33 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
46 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
2answers
82 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
43 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
55 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
3answers
39 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
80 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
111 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
35 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
17 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
95 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
31 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
vote
1answer
54 views

Time complexity for FPT algorithm

I'm studying the issue of FPT algorithms and came to the k-disjoint triangles problem as can be seen here on slide 60. The problem summary is given a graph G and variable k, are there k disjoint ...
0
votes
2answers
39 views

Analysing time complexity

Okay so we've been given an algorithm and asked to give an upper bound to its best and worst case ...
2
votes
3answers
131 views

Finding largest elements

I was asked to find write a pseudocode of an algorithm that extracts the Log(N) largest elements in an array and return them in a sorted list, my attempt is ...
2
votes
0answers
87 views

How computationally hard are the battle systems of Paper Mario and Paper Mario: The Thousand Year Door?

What is the time complexity and space complexity of working out, in suitably generalised versions of the battle systems of both Paper Mario 64 and Paper Mario: The Thousand Year Door: The minimum ...
0
votes
1answer
64 views

Time complexity of $L=\{a^nb^n | n \ge 1\}$

Consider the following language: $$L=\{a^nb^n | n \ge 1\}$$ I constructed the following Turing Machine: \begin{eqnarray} T &=& (Q, \Sigma, \Gamma, \delta, q_0, B, F) \nonumber \\ Q &=& ...
0
votes
1answer
21 views

Find distinct groups with no common parents

Given an array $arr$, element $arr[i]$ indicates its parent. If the element has no parent then $arr[i]=-1$. What is the optimal algorithm for finding the minimum number of groups such that no element ...
0
votes
1answer
57 views

Cost to convert one integer array into another

This question is distilled from an interview question. Given two arrays $a$ and $b$ containing $n$ integers each, change each integer in array $a$ into the corresponding integer in array $b$ by ...
0
votes
1answer
58 views

Prove NLOGSPACE$\subset$PSPACE

Condidering the proof, NLOGSPACE$\subset$PSPACE I wrote following proof: NLOGSPACE = NSPACE$(\log n)$ $\hspace{15pt} \because$ Definition of NLOGSPACE NSPACE$(\log n)$ $\subseteq$ DSPACE$(\log^2 n)$ $\...
0
votes
2answers
39 views

Is the best known algorithm for the shortest path problem for an undirected and unweighted graph $O(E)$ or $O(E+V)$?

I'm a bit confused by Wikipedia's tables of algorithms for the shortest path problem. For an unweighted graph with $E$ edges and $V$ vertices, it gives the best algorithm as breadth-first search, with ...
2
votes
1answer
31 views

Single tape TM that converts numbers from binary notation to unary

I need to construct a TM that converts a number from binary notation to unary and calculate time complexity.  I have done the first part. The idea is as follows: binary number is decremented by 1 ...
18
votes
3answers
3k views

Time complexity O(m+n) Vs O(n)

Consider this algorithm iterating over 2 arrays (A and B) size of $ A = n$ size of $ B = m$ Please note that $m \leq n$ The algorithm is as follows ...
0
votes
1answer
24 views

Analyzing parallel performance question

I was reviewing for my CS class and came across this question and answer combo that didn't have any explanation why it was correct. I'm confused on how they got the answer: We have a system to which ...
1
vote
0answers
16 views

Cycles per byte of 128-bit LCG

Let's consider 128-bit LCG with modulus $2^n$ of the form: $X_{n+1}=a \cdot X_{n} + c \mod 2^{128}$ How fast we can run it in cycles per byte? And how much of RAM it required?
1
vote
1answer
27 views

Is best case complexity big Omega of worst case complexity?

I need to prove or disprove the following claim: Given that the best case complexity of the algorithm A is $O(f(n))$ and the worst case complexity of A is $Ω(g(n))$, it follows that $f(n) ∈ Ω(g(n))$. ...
2
votes
0answers
43 views

A simple algorithm to solve the MST Sensitivity Analysis problem in linear time when the MST is a path

The problem. Given an undirected, connected, edge-weighted graph $G=(V, E_G; w)$ and a minimum spanning tree (MST) $T=(V, E_T)$ of $G$, the MST sensitivity analysis problem asks to find, for each ...
0
votes
1answer
37 views

Why do researchers only count the number of multiplications when analyse the time complexity of Matrix Multiplication?

In this article about the recent breakthough in Matrix Multiplication, it quotes Chris Umans's words: Multiplications are everything. The exponent on the eventual running time is fully dependent only ...

1
2
3 4 5
41