We changed our privacy policy. Read more.

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
2
votes
0answers
61 views

P/NP - Proof that SAT-TM is NP-complete uses certificate

To prove that SAT-TM (Turing machine emulating the satisfiability problem) is NP-Hard $$\text{SAT-TM}:=\{⟨M,p,1^k⟩ \; | \;∃c,\; |c|\leq p(k), \;\text{such that M accepts c in ≤k steps}\}$$ my ...
1
vote
2answers
31 views

Given a list of vertices in a binary tree output minimal sublist with the same lowest common ancestor

The input: a binary tree and a list $L$ of vertices in that tree. The output: a sublist of $L$ of minimal length that has the same lowest common ancestor as $L$. If there is several sublists of ...
1
vote
1answer
80 views

Counting letter frequency in array in O(1) with hash function

I want to calculate the frequency of each character in an array. (e.g ['a', 'b', 'o', 'p'] There are several ways to do this: A Simple brute-force over the array would need $O(n^2)$ time and $O(n)$ ...
0
votes
1answer
56 views

Finding the Big-O and Big-Omega bounds of a program

I am asked to select the bounding Big-O and Big-Omega functions of the following program: ...
4
votes
2answers
57 views

Finding which functions are bounded by $O(n^2)$

I am asked to select the functions that are bounded by the Big-Oh function O(n^2): $f(n) \in O(n^2)$. $f(n) = \sum_{i=1}^{n} n$ $f(n) = \sum_{i=1}^{n} i$ $f(n) = n + n^2$ $f(n) = 1$ I choose the ...
0
votes
1answer
16 views

Relaxation possibilities of the lower bound worst case sorting algorithms without quantum computation

The sorting algorithms (merge-sort, quicksort...) are tought to have an absolutely hard lower bound which can not be outperformed by computation alone and this bound is $n*log_{2}(n)$, The reason for ...
1
vote
1answer
41 views

Why is the Kth Largest Element solution using a MinHeap O(N lgK) in complexity?

This is a rather well known solution to the $k$-th order statistic problem which requires us to find the $k$-th largest number in an unsorted array with $n$ elements where $1 \leq k \leq n$: ...
0
votes
1answer
65 views

How to analyse the worst-case time complexity of this algorithm(a mix of Bubble Sort and Merge Sort)?

Suppose I have a sorting algorithm that sorts a list integers. When the input size(the number of elements) $n$ is odd, it sorts using Bubble Sort and for even $n$ it uses Merge Sort. How do we perform ...
1
vote
1answer
46 views

Asymptotic growth of a series

How we can prove that: $$ \sum_{k=1}^{c \log n-1}\:k\cdot \left(\frac{1}{2}\right)^{\frac{k}{3}}\in O\left(1\right) \quad \mbox{?} $$
1
vote
2answers
41 views

Compute average case with best case

is it correct to compute the average case time complexity of an algorithm by taking the mean of the best and worst cases ? My findings : for binary search, $\frac{\log (n) +1}{2}\in \Theta \left(\log (...
1
vote
2answers
114 views

Time complexity of comparing $N$ strings

I would like to double check myself. As I understand time complexity of comparing two strings in the worst case is $O(n)$, where $n$ is the length of the strings (let's say they are equal length). In ...
0
votes
0answers
21 views

It is possible proove the complexity of each query in a Segment Tree to O(log N) with recursion tree

Maybe the title is bad format but, I want to ask if is possible proof the Segment Tree complexity with the recursion tree. In other words I'm making a simple report on segment tree and I want to try ...
0
votes
0answers
40 views

In-place linear sort of integers, again

I am amazed by the many discussion regarding the existence of any linear and in-place sorting algorithm, and variants, see e.g. is-this-implementation-of-bucket-sort-considered-in-place is-counting-...
2
votes
1answer
39 views

Clarifying the definition of reduction with regards to NP-complete problems

In my logic class we started learning about the different complexity classes. In particular, we focused on the NP complexity class. A problem is in NP if it is solvable in polynomial time using a ...
1
vote
0answers
40 views

Approximating the Levenshtein distance between two binary strings using the Fast Walsh-Hadamard Transform

I have come up with a simple technique of approximating the Levenshtein distance between two binary strings using the fast Walsh–Hadamard transform: given two binary strings $a,b$ with Walsh–Hadamard ...
0
votes
2answers
40 views

Prove that $ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $ is $O(5^n)$

I need to prove that the following recurrence relation is $O(5^n)$: $$ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $$ And $T(n)=\Theta(1)$ for $n\le 9$. I am trying induction, and proving that there ...
3
votes
1answer
50 views

surprizing reducibility and challenge on it

Assume that Problem $A$ is polynomial-time reducible to problem $B$. Claim 1: If problem $A$ is NP-hard then problem $B$ is NP-hard. Claim 2: If problem $B$ is NP-hard then problem $A$ is NP-hard. ...
1
vote
1answer
53 views

optimizing the calculation of $\sum^n_{k=2} p(\Omega(k))\Omega(k)$

I want to optimize an algoritm for calculating $g(n)=\sum^n_{k=2} p(\Omega(k))\Omega(k)$ where $$ p(n) = \begin{cases} 1 &\text{if $n$ is odd} \\ -1 &\text{if $n$ is even} \end{cases}$$ and $...
2
votes
0answers
24 views

Central Trinomial Coefficients best time complexity

What is the fastest known time complexity for computing central trinomial coefficients? Let $C_n=1,1,3,7,19,51,...$ (OEIS A002426) denote the coefficient of $x^n$ in $(x^2+x+1)^n$ starting at $n=0$. ...
2
votes
1answer
46 views

Intuition on O(number of leaves) for master theorem

I am trying to develop the intuition of the master theorem for the case where $a > b^{d}$ [Case 3] in this video. In the video, they say that since most of the work is done at the leaves, we should ...
1
vote
2answers
51 views

How to index a tree to allow efficient search for paths?

By "indexing" I mean assigning addresses or labels or whatever to nodes to make them easier to locate, similar (in its effect, not necessarily in the implementation) to how a database can be ...
1
vote
1answer
78 views

Find Optimal Permutation/Positioning to Minimize the Total Distance for a Given Path

Summary: A task for picking certain objects is given in the form of an ordered sequence (eg. to pick apple, banana, apple, apple, orange, order matters). The objects have to be preassigned to certain ...
0
votes
1answer
333 views

Best algorithm (Time Complexity) to find Minimum spanning tree of an complete, positive weighted, undirected, graph

Suppose that we have a complete undirected positive weighted graph $G = \langle V, E\rangle$. What is the most efficient algorithm, in terms of time complexity, to find an MST for $G$? The best prime ...
1
vote
1answer
73 views

I don't get why the time complexity of insertion on a linked list is O(1)

I was watching the algoritmhs course by mycodeschool and he said that when we add a new item on a given position the worst case would be $O(n)$. Everywhere I look says insertion is $O(1)$... Now I ...
1
vote
2answers
92 views

What are the units for time complexity graphs?

I often see big-O notation for time complexity algorithms and I see an equation that looks like $O(n) = n\log n$, which naturally generates a graph like the bottom one: I know the x-axis represents ...
1
vote
1answer
92 views

Time complexity of a recursive function which generates all combinations of an array

The following function getCombinations, is a recursive function that can be used to generate all combinations of an array. How exactly can we find the time complexity of this function? I would ...
0
votes
1answer
68 views

How to calculate O-Notation?

I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; What I would like to ask, if there is a certain way to find out O-Notation? Actually ...
2
votes
1answer
134 views

Comparing two algorithms for all-pairs shortest paths

I read in my notes: If we use Dijkstra $|V|$ times ($|V|$ number of vertices) for finding all-pairs shortest paths in graph $G$, we get time complexity for Dijkstra algorithm as $O(VE+ V^2 \log V)$, ...
0
votes
0answers
66 views

what is the time complexity of Leiden Algorithm?

I am not able to find out the time complexity of the Leiden Algorithm. Can anyone here help me? https://doi.org/10.1038/s41598-019-41695-z.
0
votes
1answer
56 views

Run-time of a summation function and its complexity

I am trying to analyze the running time of the following function: ...
0
votes
1answer
61 views

How efficient of this prime sieving algorithm?

I just found there is an old program of mine where I implemented the following prime sieving algorithm: ...
1
vote
1answer
51 views

Runtime Complexity of Memoization

I am struggling to analyze the runtime complexity of the following algorithm formally: Given a string s and a dictionary of words dict(wordDict), add spaces in s to construct a sentence where each ...
2
votes
1answer
62 views

Prove that $\mathsf{P} \neq \bigcup_{k=1}^{\infty}\mathsf{DSPACE}(\log^k n)$

Prove that $\mathsf{P} \neq \bigcup_{k=1}^{\infty}\mathsf{DSPACE}(\log^k n)$. Hint: Assume that there is an equality, show that this implies $\mathsf{DTIME}(n^{\log n})\subseteq \mathsf{P}$ via a ...
1
vote
1answer
121 views

Time complexity of Tsp using DP

this is the recursion formula for problem : C(i,S) = min { d(i,j) + C(j,S-{j}) } In fact, when I tried to implement it as a code, the following code came to my ...
0
votes
1answer
503 views

Find amount of elements greater then number k in a BST

I am trying to find an Algorithm to find the amount of elements in a BST which are greater than a certain number K. I found it problematic as there are elements which might be greater then K but wont ...
1
vote
1answer
43 views

Bit complexity of $n$-th Fibonacci number using matrix multiplication

I want to find the bit complexity of finding the $n$-th Fibonacci number using the matrix multiplication method. I know that it has complexity $O(\log n)$ if we assume that the standard operations ...
1
vote
0answers
26 views

Connection between convergence complexity of gradient descent and complexity of exactly solving convex program?

Let $f: \mathbb{R}^n \to \mathbb{R}$ be a convex function. Let $V \subseteq \mathbb{R}$ be some closed convex set. Consider the following convex minimization problem: \begin{align} \min_{\mathbf{x} \...
0
votes
1answer
100 views

What is the time complexity of the original Otsu's method?

I'm trying to give a general comparison of the time complexities of various thresholding algorithms. I have not taken an algorithms course yet, so please forgive any misunderstandings. Otsu's method ...
1
vote
0answers
25 views

Different definitions of Exponential Time Hypothesis

I am reading basics of Exponential Time Hypothesis (ETH). There are two statements for it: Statement 1 There exists no $2^{o(n)}$ algorithm for $3$-SAT, where $n$ is the number of variables. Statement ...
3
votes
0answers
18 views

Spanning hypertree which connects the vertices as slowly as possible

I want to find a reference for the following problem or a similar problem for my paper. I found a greedy algorithm for this problem, but writing such an algorithm in a paper is not common in my area, ...
0
votes
1answer
44 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
1answer
53 views

An algorithem for finding the number of primes of the form 4k+3 under some n

I was given the task to make an algorithem that can compute the number of prime's of the form 4k+3 under some n, it should be able to compute how many number's of this type are there under 10^8 (100 ...
0
votes
1answer
35 views

What parameter of optimizations, like time solving, can be used to show a phase transition in NP-hard problems?

Before asking the question, I should say that I am not sure here is a proper community to ask this question or not. I have an NP-hard problem and an optimization to deal with the problem. Recently, I ...
0
votes
2answers
59 views

Solving $T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n$ without the Master Theorem

I want to solve $$T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n,$$ with base case $T(n) = 1$ if $n \leq 1$. I know that the solution is(with the help of the Master Theorem) $$\...
0
votes
0answers
35 views

answers Average case analysis of linear search

Suppose we have an array$[1..n]$ and run linear search to find $x$, on it with following specification: probability of existence $x$ in first half of array is $p$,and probability of existence $x$ in ...
0
votes
2answers
77 views

Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$

Prove by induction that $T(n)=\Theta(n^2 \log_{3}n)$ where $$T(n)= \begin{cases} 1 & \mbox{if } n=1,\\ 9T(\lceil n/3 \rceil)+n^2 & \mbox{otherwise.} \end{cases}$$ The base case for $n=1$ seems ...
1
vote
2answers
99 views

Solving T(n) = 2*T(n-1)+4 witht the Master Theorem

I am wondering if there is a way to solve a recurrence time function with the master theorem if no $b$ exists. Like in this case. $$ T(n) = 2\times T(n-1)+4$$
0
votes
1answer
144 views

Analysis of updating vertex and one example?

I see the following image on google: And I want to find Amortized Cost for Updating of each vertex on Dijkstra algorithm. I have an answer $O(E/V)$. I'm get stuck it means at this answer we should ...
1
vote
1answer
44 views

Average of all sums of subarrays

I ran into a very hard question. We have array of $n$ integers. for $1 \leq i \leq j \leq n$. we want to set $c_{ij}$= Sum of all values in the range $i$ to $j$ of this array. we want to finding ...
1
vote
0answers
24 views

Configuration of a space bounded turing machine

A configuration of a Turing machine is defined as the following: an ordered triple $(x, q, k) ∈ Σ^* × K × N$, where $x$ denotes the string on the tape, $q$ denotes the machine's current state, and $k$...

1
4 5
6
7 8
42