# 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.

2,162 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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, ...
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 (...
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 ...
22 views

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 ...
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 ...
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 ...
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 ...
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?
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))$. ...
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 ...
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 ...
25 views

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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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. ...
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 ...
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$, ...
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)...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
### 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 ...