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
0
votes
1answer
47 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
148 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 ...
5
votes
1answer
105 views

Searching a Treasure

I was selected for a UG interview and the following was one of the questions asked: "Suppose we have an $8 \times 8$ grid. Under one of the blocks, I (the interviewer) have hidden a treasure ...
1
vote
1answer
29 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
57 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 ...
3
votes
1answer
115 views

Survival algorithm for Network deterministic failures

Consider an undirected network $G = (V,E)$ in which edge $e$ $\in$ $E$ fails after (deterministic) time $t(e) > 0$. Network failure occurs at the first instant in which $G$ is no longer connected. ...
2
votes
1answer
104 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
42 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
607 views

Finding all unique paths from a source to a sink in a specially-formed DAG

Let $G$ be a directed, acyclic graph of order $n$, such that: $G$ has exactly one source vertex $s$; $G$ has exactly two sink vertices $t_1, t_2$; The out-degree of any non-sink vertex in $G$ is ...
1
vote
1answer
36 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
2answers
757 views

Explanation of O(n2^n) time complexity for powerset generation

I'm working on a problem to generate all powersets of a given set. The algorithm itself is relatively straightforward: ...
2
votes
1answer
38 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 ...
0
votes
1answer
593 views

Determine if an NFA accepts infinite language in polynomial time

Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite. (Note that converting NFA to DFA is exponential time). For any DFA,...
0
votes
1answer
43 views

Proof for time complexity of Insertion (k-proximate) Sort equals O(nk)

The following is the definition for Proximate Sorting given in my paper: An array of distinct integers is k-proximate if every integer of the array is at most k places away from its place in the array ...
0
votes
1answer
47 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
32 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
1answer
86 views

How to solve recurrence $T(n) = 5T(\frac{n}{2}) + n^2\lg^2 n$

I have tried solve the recurrence $T(n) = 5T(\frac{n}{2}) + n^2\lg^2 n$ using substitution. Apparently, it is exact for some $n$ and the order of the general solution can be found from this exact ...
2
votes
2answers
154 views

Is there a defined set of steps or principles on how to reduce time complexity of algorithms?

I have been watching some big (Google, Facebook,..) company interview examples and usually when pair programming, they develop the most straightforward algorithm and then the interviewer asks 'could ...
1
vote
1answer
175 views

Recursion Time Complexity (Half n' Half)

This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity: Input: string $s = s_1,\ldots,s_n$, integer $k$ Go over all symbols $s_1,\ldots,s_n$, one by one ...
0
votes
1answer
19 views

speed of preorder traversal

I want to know the speed of preorder traversal of an tree. I do not mean its order of magntude which we know is O(n). I want something like 27n operations where an operation is precisely defined. ...
0
votes
1answer
60 views

Upper bound for runtime complexity of LOOP programs

Recently I learned about LOOP programs, which always terminate and have the same computational power as primitive recursive functions. Furthermore primitve recursive functions can (as far as I ...
0
votes
1answer
39 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
19 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
23 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
2answers
109 views

Proving complexity of $T(n)=2T(n/3 + 1) + n$ non-Akra-Bazzi

We know that the complexity of $T(n)=2T(n/3 + 1) + n$ is $\Theta(n)$, as has been proved on this exchange before. However, what about proving it inductively? I believe that this method might work. ...
1
vote
0answers
18 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
34 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 ...
2
votes
1answer
117 views

How to estimate the average time complexity of greatest common divisor?

As we know, the time complexity of $\gcd(x,y)$ is $O(\log \min(x,y))$ by using Euclidean algorithm. Now we fix a constant $n$ and consider the average time complexity of $\gcd(x,n)$. Formally, let $f(...
0
votes
1answer
63 views

$ \Omega(m)$ and $O(m)$ meaning in theorem proof about dynamic array complexity

My algorithms and data structures' book states that to create a dynamic array the following procedure is followed: Let $d$ be the length of an array $ a $ and $n $ the number of elements stored in ...
0
votes
0answers
33 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
1answer
62 views

Given $n$ unique items and an $m^{th}$ normalised value, compute $m^{th}$ permutation without factorial expansion

We know that the number of permutations possible for $n$ unique items is $n!$. We can uniquely label each permutation with a number from $0$ to $(n!-1)$. Suppose if $n=4$, the possible permutations ...
8
votes
2answers
526 views

Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?

I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in ...
1
vote
2answers
64 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
26 views

asymptotic tight bounds for quadratic functions

In Introduction to Algorithms by CLRS, it's said For any quadratic function $f(n)=an^2+bn+c$, where $a$, $b$ and $c$ are constants and $a>0$, $f(n)=\Theta (n^2).$ Formally, to show the same thing, ...
0
votes
1answer
46 views

Time complexity of $a^{n^b}; a,b>1$

What ist the time complexitiy of an algorithm with the running time of $a^{n^b}; a,b>1$? And how is it compared to factorial complexity O(n!)?
0
votes
1answer
718 views

Time complexity of quicksort for arrays in increasing or descreasing order

Two $n$-size arays are given: $n_1$ is in decreasing order and $n_2$ is in increasing order. Let $c_1$ be the time complexity for $n_1$ using quicksort, and $c_2$ the time complexity for $n_2$ using ...
1
vote
1answer
39 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
18 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
votes
1answer
35 views

Time complexity of a machine which combines Insertion Sort and Quicksort

Given a machine that sorts an array of length $n$ with the following algorithm: Sort first $2\sqrt{n} + 1$ elements of array with Insertion Sort.(Check Insertion Sort) Select the median of the whole ...
0
votes
0answers
45 views

Prove that $T(n)=\omega(n)$?

Edit: can someone provide clear answer with all details Given: $T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$ I was asked to find the minimum value for $a$ for which $T(n)=\omega(n)...
2
votes
1answer
2k views

To find median of k sorted arrays of n elements each in less than O(n*k*log(k))

How to find median of k sorted arrays each of length n? Note that total elements would be n*k. I know it can be done in O(n*k*log(k)) using merge technique. I am looking for a better time efficient ...
2
votes
2answers
77 views

Examples of higher order algorithms ($\mathcal{O}(n^4)$ or larger)

In most computer science cirriculums, students only get to see algorithms that run in very lower time complexities. For example these generally are Constant time $\mathcal{O}(1)$: Ex sum of first $n$ ...
0
votes
1answer
58 views

Explanation of pseudocode and time complexity analysis

I am trying to work my way through some computer science training and I am not able to properly understand the following pseudo code: ...
1
vote
1answer
167 views

Why log-space reduction is used for NL-completeness while PSPACE reduction isn't used for PSPACE completeness?

NL-Complete languages are defined by Log-space reduction, while PSPACE complete languages are defined by poly-time many-to-one reduction. According to these posts : Why not polynomial-space reductions ...
1
vote
1answer
49 views

If $f(n) = O(g(n))$ then $\log\lfloor f(n) \rfloor = O(\log \lfloor g(n) \rfloor)$?

I need to prove that $\log\lfloor f(n)\rfloor = O(\log\lfloor g(n) \rfloor)$ if $f(n) =O(g(n))$. I know that if $f(n) = O(g(n))$ then $\log f(n) =O(\log g(n))$, but I can't prove the current statement ...
3
votes
0answers
34 views

What's the best non-amortized disjoint set?

In practice, the amortized O(α(n)) data structure is good for every case. But if I want to be pedantic and require each operation to be under a certain time complexity, what's the currently known best ...
0
votes
1answer
24 views

Runtime Analysis: What grows faster?

I was wondering which runtime is a tight upper bound for $f(n,m)= n^2 + 1/2^k$ with $k = n - m$ Intuitively I thought that $f(n,m)$ is in $O(n^2)$ but the longer I am thinking about this the more I ...
1
vote
1answer
20 views

Lower bound for matrix determinant algorithm

I have the an algorithm for computing a matrix determinant: $$\ det(A) = \sum_{i=1}^n (-1)^{i-1} \cdot A_{i1} \cdot det(A_{-i,-1})$$ Where $\ A_{-i,-1} $ is the matrix $\ A $ without the row $\ 1 $ ...
0
votes
0answers
10 views

Complexity of a cutting operation on a list of binary trees

Consider a list of full binary trees of heights $(h_0, h_1, \ldots, h_{n-1})$ where a tree with a single leaf is deemed to have height 0. The list has the property that the height of the tree when ...

1 2
3
4 5
38