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
-1
votes
1answer
40 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
23 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 ...
0
votes
1answer
49 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
62 views

Complexity of generating power sets

Suppose I have two sets $A$ and $B$ containing integers. Let $B'$ be the power set of $B$. Then suppose I have an algorithm that enumerates all possible pairings of elements in $A$ and $B'$ to apply a ...
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
3answers
86 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 ...
0
votes
1answer
35 views

Help with model answer for time complexity

Hi I cannot understand why the best case for line 3 is n-1 and why it isnt just always n? I tried to write this in python to ...
1
vote
0answers
34 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 ...
2
votes
1answer
142 views

Complexity of generating non-uniform random variates

What can we say about the complexity of generating (negative) binomial and (negative) hypergeometric random variates? In particular, it is possible to generate (negative) binomial and (negative) ...
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
35 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 ...
1
vote
1answer
65 views

What would be the practical consequences of ZPP=exptime

What would be the practical consequences of ZPP=exptime. It would be pretty ridiculous if the was true but what if it was?
0
votes
2answers
23 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
1answer
77 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
0answers
56 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, ...
1
vote
1answer
292 views

CRC computation speed vs polynomials features

I tried to find information about how features of a CRC polynomials influence computation speed of implementations. It is obvious that (depending from the CPU architecture the algorithm runs on) ...
-1
votes
0answers
19 views

Time Complexity for finding k disjoint triangles in a colored graph [duplicate]

Input: A colored graph G=(V,E) s.t(for every v∈V, v gets a random color between [1,3k] and an integer k∈N. Output:Are there k vertex-disjoint triangles in G? Required Running time: O∗((2)3k). the ...
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 ...
5
votes
1answer
607 views

How can there be undecidable languages in P/1?

I didn't understand some things about $ P/POLY$ class, and I will be thankful if you could help me. as I learned in class, a turing machine M accepts language L with advice $ {a_n} $ if $\qquad\...
0
votes
1answer
18 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
10 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
1answer
22 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
38 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 ...
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 <= n The algorithm is as follows ...
0
votes
2answers
37 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 ...
1
vote
2answers
106 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 ...
0
votes
1answer
53 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 &=& ...
2
votes
1answer
25 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 ...
1
vote
2answers
623 views

Modular exponentiation running time

I read on Wikipedia that modular exponentiation can be done in polynomial time. I've a few questions regarding it (sorry if they seem a bit easy – I'm not a comp sci student). Is it poly ...
0
votes
1answer
46 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
1answer
20 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
2answers
32 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 ...
0
votes
1answer
39 views

$O(n^2)$ and $O(n\log n)$ exercise [duplicate]

There is an exercise which says : Al and Bob are arguing about their algorithms. Al claims his $O(n \log n)$-time method is always faster than Bob’s $O(n^2)$-time method. To settle the issue, they ...
0
votes
1answer
15 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
15 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
23 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))$. ...
3
votes
0answers
30 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
51 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 ...
0
votes
1answer
32 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 ...
0
votes
1answer
170 views

How to prove the optimization version problem (whose decision version is NP-complete) can be solved in poly-time iff P=NP?

I have proved the decision version of my problem to be $\mathcal{NP}$-complete. And I know that if I can solve the optimization version in poly-time, then I can just compare the obtained minimum (or ...
1
vote
1answer
17 views

Can PTAS $\epsilon$ parameter be dependent on the algorithm input?

Let A be a PTAS algorithm with time complexity $O\left(\frac{1}{\epsilon}\right)$. Let $n$ be the input of the algorithm A. From Wikipedia: The running time of a PTAS is required to be polynomial in $...
1
vote
1answer
40 views

Is Vertex Cover of size $k >100$ polynomial time solvable?

I know that when we want to find out if Vertex Cover of size $k$ when $k \leq C$, belongs to P or not (when $C$ is some constant), we actually can find algorithm with polynomial time complexity (in ...
-4
votes
0answers
35 views

How do I write this recurrence relation?

Write the recurrence relation of the following algorithm and solve it using iteration method. Use initial value of T as 2. The complexity of swap function is O(1). ...
1
vote
1answer
54 views

Average number of comparisons for a successful search of a prime number in a binary search tree

A binary search tree is constructed by inserting the following value sequentially: $$3, 9, 1, 6, 8, 7, 10, 4, 2, 5$$ Let $p_v$ be the probability to search for the value $v$ in the binary search tree (...
-1
votes
0answers
29 views

Prove that the problem of finding the k-th power of n is a P problem

I got following problem as an exercise. Prove that the problem of finding the k-th power of n is a P problem, assuming that the multiplication of two numbers can be completed in unit time. I just ...
-1
votes
2answers
44 views

Big-O-notations and Small-o-notations

$a)$ Determine for all pairs $i$ and $j$, $i,j ∈ \{1, \ldots, 6\}$ whether for the ones given below functions $f_i ∈ O(f_j)$ or $f_i ∈ o(f_j)$ or neither of the two applies as $n → \infty$: $f_1 = \...
1
vote
1answer
48 views

Time complexity of algorithms

I have some questions that I don't understand about time complexity. Given that the worst case complexity of the algorithm $A$ is $O(f(n))$ and the best case complexity of $A$ is $Ω(g(n))$. It ...
1
vote
3answers
95 views

An $O(n^2)$ is faster than an $O(n\log n)$ algorithm for small $n$

If $n<100$ then $O(n^2)$ is more efficient, but if $n\ge 100$ then $O(n\log n)$ is more efficient. I am sure that this statement is valid, but I don't know how to prove it or justify it. Can ...
1
vote
0answers
21 views

Effect of determinization on the time complexity of Turing machines

Suppose I assume that the complexity of a non-deterministic Turing machine $N$ is $T(n)$, $n$ is the length of the input string. What would be the time complexity of a deterministic Turing machine $D$ ...
1
vote
1answer
18 views

Time complexity of finding median in data stream

I was reading a solution to the problem in the title on leetcode and the article says that the time complexity of the following solution is O(n) setup a data structure to hold stream value and insert ...

1
2 3 4 5
40