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
19 views

What is the time complexity of the Edmonds-Karp algorithm for finding a maximum cardinality matching in bipartite graphs?

What is the time complexity of the Edmonds-Karp algorithm (not the Hopcroft-Karp algorithm) for finding a maximum cardinality matching in bipartite graphs? Is it still $O(|V||E|^2)$, or it has a ...
0
votes
1answer
35 views

Does $f(n)=\theta(g(\log{n}))$ imply $f(n)=\theta(\log{g(n)})$?

I am learning about algorithmic complexities and I have this claim which I need to prove or disprove: $f(n)$ and $g(n)$ are asymptotically positive functions, if $f(n)=\Theta(g(\log(n))$ then $f(n)=\...
7
votes
1answer
810 views

Algorithms that run in polynomial time if P=NP

On Wikipedia, it says that that there are some algorithms that would run in polynomial time if and only if P=NP. They gave one example (without citation), but are there any others? I tried looking ...
0
votes
1answer
24 views

If there is an polynomial time approximation to an NP-complete problem, is P approximately NP?

Deciding bipartite hypergraph coloring is NP-hard: While for bipartite graphs a 2-coloring can be found in linear time, it was shown by Lovasz [10] that the problem to decide whether a given k-...
0
votes
2answers
45 views

Can you insert into sorted list with time O(1)?

Wondering if this was possible. If I have a sorted list, can I find the right spot for an integer and insert it, all in O(1) time? The only way I can think to do this is via having a MASSIVE hashmap ...
1
vote
2answers
62 views

Probability that two elements are compared in randomized quicksort

I am having an issue in a specific part of the randomized quick-sort analysis. As per the randomized quick-sort algorithm the pivot is chosen from the given subset on which it is called from a random ...
-1
votes
1answer
60 views

Merging $t$ arrays of size $t$ cannot be done in $O(t^2)$

Dr. John claims that he designed a comparison-based algorithm FastMerge that can merge $t$ arrays of size $t$ at most each in $O(t^2)$ time. In Dr. John’s own words, ”Given $t$ sorted arrays $B_1,B_2,...
1
vote
0answers
17 views

Why does this BFS solution work for this question about euclidean distance and what's its complexity?

Given a matrix of 1s and 0s where 0 represents houses and 1 represents stores, find the square of minimum Euclidean distance of every house to nearest store. Return it as a vector of vector. ...
2
votes
1answer
18 views

Is two-coloring parts of a bipartite graph so that for each uncolored vertex, the incoming edges from each color are roughly equal NP-complete?

Let's say we have a bipartite graph $G=(V_1\dot\cup V_2,E)$. We're now looking for a two-coloring (red/blue) of the vertices of $V_1$, so that for all vertices $v\in V_2$ the sum of edges coming from ...
-2
votes
0answers
16 views

I want to know the complexity of this following code [closed]

include include include void main() { char p[10][5],temp[5]; int i,j,pt[10],wt[10],totwt=0,pr[10],temp1,n; float avgwt; printf("Enter no of girls:"); scanf("%d",&n); for(i=0;ipr[j]) { temp1=pr[...
0
votes
0answers
17 views

How to generate unique keys for different two dimensional matrices having different sizes?

No. of rows in the table (as given in image) is not known beforehand . The problem I am dealing with generates different 2-D matrices based on the input data given. As soon as a matrix generates it ...
0
votes
1answer
109 views

Remove range of keys from Binary Search Tree in O(s+h)

I have a binary search tree with integer keys. I have to remove a range (m, n]eZ of keys from the BST in O(s + h) where s is the number of keys to remove and h is the height of the tree. Attempted ...
0
votes
1answer
21 views

Shortest path form node X to nodes A, B, C in graph

I have an unweighted consistent graph and some node X(the source) and some nodes A, B, C and more. I need to find the shortest paths: X->A, X->B, X->C and ...
1
vote
1answer
24 views

Algorithmic problem with many different time/space complexity solutions

I am preparing a lesson about algorithmic thinking for beginner programmers. I would like to show them an easy to understand problem which has as many solutions as possible with different time or ...
-2
votes
0answers
20 views

What is the Big-O runtime of this algorithm? please [closed]

val<- 0 for(i = 0; i < n; ++i) { for (j = n; j > i; --j) { val++; }
0
votes
1answer
41 views

How to shift a matrix by x rows and y columns in the most efficient way?

My objective is to shift rows by x and columns by y in a 2d matrix. My problem is to solve this objective in an efficient manner. x and y could be negative or positive. Negative would mean up/left ...
1
vote
1answer
19 views

Complexity of finding factors of factors of N number

for (int i = 1; i <= N; i++) for (int j = i; j <= N; j+=i) for(int k = j; k <= N; k+=j) How to express this mathematically to calculate the ...
1
vote
1answer
16 views

Consequences of the Time Hierarchy Theorem

The form of the Time Hierarchy Theorem that I have is this: If $f$ is time constructible then $\text{DTIME}(f(n)) \subsetneq \text{DTIME}(f(2n+1)^3)$. We want the consequences of this to be that $\...
0
votes
1answer
51 views

Amortized value of dequeue with potential function

A deque is implemented with 3 stacks. one for the head, one for the tail and one is always empty. Pushing is therefor O(1), light popping (in case the head/tail respectively aren't empty) is also O(1)....
1
vote
1answer
20 views

Can someone let me know if my understanding of amortized run time in a dynamic array list is correct?

Am I right in my understanding for amortized time for insertion in a dynamic array list? (dynamic means create a copy double its size and copy existing elements to new one WHEN we reach the current ...
3
votes
1answer
40 views

Is there a complexity class QPP?

The complexity class PP is not considered tractable, because the probability of success can get arbitrarily close to 50% from above as the problem instances get larger, so that (e.g. if this approach ...
0
votes
1answer
37 views

Complexity class of an algorithm

What is the complexity class of an algorithm that runs in $n^{\mathcal{O}(\sqrt{n}log(n))}$ time? As $n$ gets large $\sqrt{n}log(n)$ increases at a very slow rate. Does this mean that the algorithm ...
2
votes
1answer
31 views

Subset of $k$ vectors with shortest sum, with respect to $\ell_\infty$ norm

I have a collection of $n$ vectors $x_1, ..., x_n \in \mathbb{R}_{\geq 0}^{d}$. Given these vectors and an integer $k$, I want to find the subset of $k$ vectors whose sum is shortest with respect to ...
1
vote
2answers
86 views

Solving equation with $n\log n$

Given a computer that takes 1 microsecond for an operation, I'm trying to find the amount of operations this computer can perform in one second, given an algorithm with complexity $O(n\log n)$. I've ...
0
votes
0answers
54 views

What is the Big theta of $(\log n)^2+2n+4n+\log n + 50$?

$f(n)=(\log n)^2+2n+4n+\log n + 50$ I am trying to mathematically prove that $f(n)$ falls under some time complexity big theta. My guess is that it is $(\log n)^2$ because it is the dominant term. I ...
18
votes
7answers
3k views

Why do we use the number of compares to measure the time complexity when compare is quite cheap?

I think one reason a compare is regarded as quite costly is due to the historical research as remarked by Knuth, that it came from tennis match trying to find the second or third best tennis player ...
1
vote
1answer
60 views

Time complexities of state-of-the-art SAT solvers with respect to length of the formula

I am learning about DPLL and CDCL SAT solvers, and I know that they have time complexity exponential to the number of variables. If I am not mistaken, one of the reasons why most believe P does not ...
1
vote
0answers
18 views

Maximum edge-disjoint flow

Consider the case where you have two types of flow, let's say "red" flow and "blue" flow. You want to send $k_r$ red flow and $k_b$ blue flow through a DAG $G$ from a source $s$ to a sink $t$ in such ...
0
votes
1answer
36 views

Perfect Matching in Bipartite Graph with mutually exclusive edges

Problem I would to solve Perfect Matching in Bipartite Graph Problem where some edges are mutually exclusive. Example Left vertices: $a,b,c$ Right vertices: $x,y,z$ Edges: $(a,x),(a,y),(b,z),(c,y)...
1
vote
1answer
52 views

Sum of sequence complexity

I try to find out what is the time complexity of this program: ...
2
votes
1answer
47 views

LaTex Text Justification badness penalty

I had been going through dynamic programming concepts and happened to read about text justification problem in which the spaces to the right of the line end are penalized with cubic times the number ...
1
vote
1answer
17 views

Argument in proving that function is not polynomial time in bit length of input seems faulty

I am currently solving a question that asks which of the following functions can be calculated in polynomial time: $$n!, \binom{n}{5}, \binom{2n}{n}, n^{\lfloor \lg n \rfloor}, \lfloor \sqrt{n} \...
0
votes
0answers
16 views

Stochastic Outlier Selection (SOS) time complexity

I cannot find the time complexity of the Stochastic Outlier Selection (SOS) algorithm derivad by J.H.M. Janssens, F. Huszar, E.O. Postma, and H.J. van den Herik. Stochastic Outlier Selection. ...
0
votes
1answer
26 views

Does the language defined in the details in NP-C or P?

It's known that: $$ \textrm{CLIQUE} = \{(G,k): \mbox{G has a clique of size } k\} $$ is $\textrm{NP-C}$, but what if every vertex has 2 neighbours (as defined in $\textrm{2d-CLIQUE}$)? $$ \textrm{2d-...
1
vote
3answers
49 views

NP-complete problem 3-SAT, is there a difference in complexity between just providing yes/no without exact solution

The 3-SAT problem is NP-complete, meaning that no known algorithm can provide an exact solution in polynomial time, while a solution can be tested very quickly in polynomial time. My question is, ...
1
vote
0answers
58 views

Range Minimum Query with Updating values

I was wondering if the following problem can be solved in asymptotically better time than$ \ O(n \log n)$. Suppose you have an array of integers $a_1,a_2,a_3,\ldots,a_i,\ldots,a_n$ where initially ...
1
vote
0answers
65 views

Confused about O(n) and O(1)

int n = 1000; int cnt = 0; for (int i = 0; i < n; i++) cnt++; Is the above code O(n) or O(1)? If I run the above code many times, it still iterates 1000 ...
0
votes
1answer
43 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 ...
2
votes
1answer
18 views

Deriving the Time Complexity of Ryser's Algorithm for Evaluating the Permanent of a Matrix

Ryser has shown that the permanent of an $n \times n$ matrix $A=(a_{ij})$ can be expressed as \begin{align} Perm(A) = (-1)^n \sum_{s \subset [n]} (-1)^{|s|} \prod_{i=1}^n \sum_{j \in s} a_{ij}, \end{...
1
vote
1answer
48 views

Difficulty in understanding this summations to analyze time complexity

I wanna know if what this link https://stackabuse.com/shell-sort-in-java/'s calculation of the complexity of shell sort is true. Here's the shell sort algorithm: ...
1
vote
0answers
25 views

Time Complexity of a Naive Solution to Merge K Sorted Arrays

There is a leetcode question about merging k sorted arrays. I would like to be able to explain the time complexity of the following naive solution: ...
0
votes
1answer
47 views

Do exponential functions grow faster than logarithmic?

For example: $f(n) = n(log_2 n)^4$ vs $g(n) = n^{1/3}$ Does f(n) grow slower than g(n) as a general rule, even for decimal exponents? I tried doing a limit test but symbolab limit calculator is ...
1
vote
1answer
37 views

Determining asymptotic notation of a complex function

$$ 5n^4\log{n} - \frac{100n^2}{\log_4(n^2)} + 40 $$ I am currently studying algorithm analysis and i need to express this function in terms of big O, theta and omega, so I should find C, and N0 for ...
0
votes
0answers
34 views

Is time complexity of the greedy set cover algorithm cubic?

I claim that the greedy algorithm for solving the set cover problem given below has time complexity proportional to $M^2N$, where $M$ denotes the number of sets, and $N$ the overall number of elements....
2
votes
1answer
53 views

Time complexity for the 'Restore IP Addresses' problem

There's a programming problem 'Restore IP Addresses' where given a string containing only digits, restore it by returning all possible valid IP address combinations. Example, "25525511135" returns ["...
0
votes
1answer
70 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: ...
1
vote
2answers
104 views

How many times is a for loop executed?

Consider the following code snippet: for(int i=0;i<n;i++) The question I have is: whether this loop is executed $n$ times or $(n+1)$ times? According to what ...
2
votes
1answer
31 views

Recurrence Relations

I am starting to learn recurrence relations in class and I am having issue with this example: T(N) = 2N - 1 + T(N-1) I am bit confused as to get the base case. I'm sorry if this seems elementary, ...
0
votes
1answer
104 views

The hardness of solving $x^2=2$

What's the hardness of the following problem: $\textbf{argmin}_x\{|x^2-2|\}$. By analytical calculation, I know the solution is $\pm \sqrt{2}$. But I am quite confused about whether it is hard ...
1
vote
1answer
31 views

Is it possible to include numerical values or constants within brackets(time complexity)?

I am currently trying to learn a bit more about the theoretical side of computer science and I have stumbled upon this example I found online: $5n^2 + 5n = O(0.5n^2)$ I do have basic understanding ...

1
2 3 4 5
33