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
vote
1answer
62 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
50 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
90 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
137 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
71 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
22 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
105 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
36 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
64 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
44 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
152 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
108 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
95 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
39 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
62 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
90 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
72 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
41 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
4k 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
57 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
18 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
32 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
55 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
44 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
vote
1answer
25 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
114 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 ...
0
votes
0answers
162 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
2answers
48 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
57 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 ...
0
votes
1answer
61 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 ...
1
vote
3answers
245 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
1answer
29 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
vote
0answers
22 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
15 views

can't quit understand one step of the recurrence time complexity calculation

I solved the question T(n) = T(sqrt(n)) + 1 but can't quit understand one step of the solution I don't understand the transition in (1). how did we conclude that T(m) = T(m/2) + 1 from the previous ...
0
votes
1answer
87 views

How to prove that one problem belongs to class P?

Is there any typical proving method when proving that one problem belongs to class P? For example, when proving that The problem of finding n to the kth power is the P problem. (Each multiplication ...
1
vote
1answer
48 views

Time-Complexity Verification: Code with two loops with an index halved at each iteration

I have the following code in python and was asked to find the tightest upper-bound in terms of Big-O , I've done two attempts below and I don't know which one is right, can you help me verify as to ...
0
votes
0answers
41 views

Complexity of backtracking to find power set given random array of numbers

Given an array of elements which can contain duplicates, this is an algorithm that solves the problem. ...
1
vote
0answers
19 views

Polynomial Time Complexity: O(loglog n) = O(n^2)? [duplicate]

Is O(loglog n) equal to O(n^2) in polynomial time? I know O(log n) is eqaul to O(n) in polynomial time because this can change as follows: log n > 2^(log n) > n^(log 2) > n. So, my question ...
0
votes
2answers
67 views

Time complexity of a function with while loop

What is the time complexity of the following procedure? for $x \in \{1,\ldots,n\}$: $\quad$ $i \gets \lfloor n/2 \rfloor$ $\quad$ while $i \neq x$: $\quad\quad$ if $i > x$ then $i \gets i -1$, ...
0
votes
0answers
16 views

Show that the set of perfect powers belongs to P [duplicate]

An integer n > 0 is called a perfect power if there are integers a, b ≥ 2 for which n = a^b. Show that the set of perfect powers belongs to P. Is the time complexity to this decision problem O(n^2)...
1
vote
1answer
70 views

Reducibility: Show that SUBSET SUM is reducible to the following problem A

A: Given nonnegative integers x1,...,xn (written in binary), and an integer k, can the net expenses be balanced using k or fewer checks? (Suppose that A is in NP). Purpose: to reveal that SUBSET SUM ...
-1
votes
1answer
40 views

Time Complexity: Does the following problem belong to NP?

Suppose n people live in a house and wish to share their expenses equally. Their respective expenses (before settling) are x1, ..., xn. They agree to write checks to each other so as to make all their ...
0
votes
0answers
46 views

Time Complexity: Show the following problem belongs to FP

Let $n > 0$ be an integer. Show that the rounded square root function $f(n) = ⌊\sqrt n⌋$ belongs to FP. Suppose $n=x+y$, where $x$ is the largest perfect square which is at most $n$, and $y$ is ...
0
votes
2answers
71 views

Consider a 1-tape TM that starts with n ≥ 1 written in unary/binary notation on its tape. Explain how it can count down from n to 0 in O(n) steps

Consider a 1-tape TM that starts with n ≥ 1 written in unary/binary notation on its tape. Explain how it can count down from n to 0 in O(n) steps. For binary notation, if we have a binary counter ...
1
vote
1answer
60 views

Time Complexity of Memoized Solution

I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution, which I optimized using memoization. The recursive solution computes a function $u(i,m)$, depending on ...
1
vote
1answer
37 views

Theta bound for runtime analysis of nested while loops

I am trying to fully analyze the running time of $\texttt{nestedLoops}$ in terms of $n$ with a Theta bound. The Java code I have is as follows: ...
0
votes
1answer
85 views

Is the multiplicative constant in the Big O notation are ignored because of Linear Speed-Up theorem?

I just want to know if Big O notation was used as a consequences of the Linear speed up theorem or not. For me I guess the answer is yes. For example, if we didn't have a linear speed-up theorem, then ...
0
votes
2answers
37 views

Can quantum computers be modelled as a classical computer with access to an oracle?

Quantum computers can solve certain problems faster than classical computers e.g factoring numbers. and this is because quantum computers can do a fourier transform on $n$ bits in $O(n^2)$ time as ...
2
votes
0answers
54 views

Two dimensional recursive function in $O(\log n)$ time complexity

It is well known that a recursive sequence or $1$-d sequence can be calculated in $O( \log n)$ time given that it has the form $$a_n=\sum_{k=1}^{n} C_ka_{n-k},$$ where $C_k$ is a constant. Examples ...

1
3 4
5
6 7
44