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 [tag:runtime-analysis] instead. If your question concerns whether or not a computation will *ever* finish, use [tag:computability] instead. Time-complexity is perhaps the most important sub-topic of [tag:complexity-theory].

3
votes
1answer
54 views

Algorithm to compute sum of cost of all path between pair of unique vertices of a tree

Given tree is undirected graph. It has n vertices and n-1 edges. The algorithm should compute the sum of cost of all path between pair of unique vertices. Thus, there are total nC2 or n(n-1)/2 such ...
3
votes
1answer
58 views

Enumerate all paths in a given series-parallel graph

Series parallel graph is well-known and widely used. It has a single source and a single destination. The graph can be formed by means of recursive serial or parallel composition. I have a graph ...
0
votes
1answer
34 views

Online algorithm for finding of clique of size k

I am trying to write an online algorithm that can detect cliques of size k. I first start out with a set of vertices. For each iteration, I add an edge. The algorithm will detect the first time an ...
0
votes
0answers
32 views

How to prove that extended euclidean algorithm has time complexity log(max(m,n)) ?'

I tried to search on internet and also thought by myself but was unsuccessful. Intuitively i think it should be O(max(m,n)). can someone give easy explanation since i am beginner in algorithms.
2
votes
2answers
103 views

Why does coNP⊆NP∖P imply that the polynomial hierarchy collapses?

I was looking for some information on 1-in-3 SAT and came across this paper, last updated 9 days ago, which claims that the Polynomial Time Hierarchy collapses "to the level above P=NP". That's quite ...
0
votes
1answer
34 views

What impact does the modulo operator have in a for-loop?

Here's an example of what I mean: ...
2
votes
1answer
29 views

Number of equivalence classes in $P$

I am currently taking a course which involves computational complexity. I was told that polynomial equivalence (polynomial time reduction) divides P into exactly 3 equivalent classes, namely $\phi$ , $...
1
vote
0answers
14 views

How to adapt proof of the ND time hierarchy theorem for alternate definition of NDTM?

For reference, the version of the nondeterministic time hierarchy theorem in question is this one: The relevant portion of the proof in question (also from Arora-Barak) is here: Arora-Barak define a ...
4
votes
1answer
104 views

Matching Algorithm - How to maximize matched quantity with unique matching rules?

Given a set $S=\{A,B,\cdots,H\}$. Elements in $S$ can be matched according to the following rules: $$\begin{aligned} A\leftrightarrow B\\ C\leftrightarrow D\\ B+C\leftrightarrow F\\ D+A\...
3
votes
1answer
43 views

How to calculate Big O of $T(n) = aT(n^b) + f(n)$?

I'm a student studying Big O. I know that we can solve $T(n) = aT(\frac{n}{b}) + f(n)$ by compering $n^{\log_b{a}}$ to $f(n)$ or $O(n^{\log_b{a}} + f(n))$ Today I was faced with $T(n) = T(\sqrt n)...
0
votes
0answers
27 views

count all possible paths of length n in an undirected graph with use of dynamic programming [duplicate]

Given is an infinitely large grid graph. Use dynamic programming to calculate the number of possible paths of a given length n from a given start node, so that fjor every path applies: a) no vertex ...
0
votes
0answers
23 views

Multi-tape to single tape Turing Maching transition complexity

Suppose we have a k-tape Turing machine M and we wanna model it with a Single tape Turing machine N with a register. Suppose the time complexity of M is T(n): ...
2
votes
1answer
26 views

Complexity of a Turing Machine when changing its alphabet to binary

I found in 'Computational Complexity: A Modern approach' Book the following statement that i dont quite understand its proof: For every f : {0, 1}∗ → {0, 1} and time-constructible T : N → N, if f ...
5
votes
1answer
71 views

Searching a Treasure

I was selected for a UG interview for computational natural science program and the following was one of the questions asked: "Suppose we have an $8 \times 8$ grid. Under one of the blocks, I (the ...
1
vote
2answers
54 views

How can the length of a string be $O(\log n)$?

I have just started learning about time complexities and am currently reading Logarithmic Complexity. Here's an example of a piece of code which is $O(\log n)$: ...
0
votes
0answers
43 views

On the same group data strcture

In a particular school, $n$ students are taught, and we are given a list of interrelations between students. The teacher asks the students to divide into a maximum number of groups (on his part, ...
0
votes
0answers
33 views

$\Omega$-notation for insertion sort [duplicate]

I'm reading the CLRS book and there is a statement for instance, the running time of insertion sort is not $\Omega(n^2)$, since there exists an input for which insertion sort runs in $\Theta(n)$ ...
2
votes
3answers
213 views

Is time complexity more important than space complexity?

I've noticed quite a few cryptographic algorithms speak mainly of the time complexity of an algorithm. For example, with a hashing function h, find x given y = h(x). We normally speak on how long it ...
1
vote
0answers
24 views

time complexity of k-bubble sort [duplicate]

I'm a student. today I answered a question wrong, the question is this: Spouse we have a k-bubble sort, which means except sorting 2 elements each time, it has a magical function that can sort $k$ ...
0
votes
2answers
72 views

What is the height of a tree with recursion formula: $T(n) = T(n - \sqrt{n})$

I know if the time complexity of an algorithm is given with the above formula, then the algorithm works in constant time but my question is that what will be the height of the recursion tree for this ...
4
votes
0answers
36 views

Algorithm for Unique Selections

Suppose I have $k$ sets with $n$ elements in each. Define a selection as one element taken from each set. A selection is unique if there's one and only one way it can happen—that is, one and only one ...
2
votes
1answer
24 views

Minimize sequence storage by overlapping prefixes

I bumped into this problem today, and after a bit of pondering, I think I have a solution in $O(n^3)$, which is better than no solution or an $O(n!)$ solution, but my answer still isn't great. Can ...
3
votes
1answer
33 views

Quantum vs classic in NP-hard problems

Is there any quantum algorithm (algorithm for quantum computers) for any NP-hard problem that has better runtime than the best known classic algorithm's runtime?
1
vote
0answers
15 views

Randomized Quick Selects' time complexity dependence on k - the index to be selected

I was analyzing Randomized Quick Selects' time complexity, as a function of n - the size of the input, and k - the index of the element that needs to be selected. The time complexity dependence on n ...
1
vote
0answers
8 views

About logarithmic cost model and bit complexity model?

So I heard that there are such models for finding time complexity of an algorithm as logarithmic cost model and bit complexity model. But from the information I have found in the internet, I cannot ...
1
vote
1answer
102 views

Can I simplify successive XOR operations?

I'm doing an online programming challenge where successive XOR operations are used (from codewars.com, if you don't want to create an account, here are the instructions). We have a rectangle of known ...
0
votes
0answers
13 views

Is the Time Complexity of Trial Division Exponential? [duplicate]

I know that there is already a similar question asked on here, but after reading the wiki page on trial division, I am confused, and the other answer doesn't help. The wiki page states that when doing ...
3
votes
1answer
100 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 ...
-3
votes
2answers
43 views

BigO time complexity of 3 nested for loops

I'm debating with a friend whether a particular function I wrote is $O(N^3)$ or $O(N \times M \times X)$ I believe it is the latter since all 3 variables differ in size. $N = 100, M = 50, X = 10000$ ...
2
votes
1answer
25 views

Definition(s)/characterization(s) of intractability

I've been searching around for definitions of intractability, and I realized that despite being widely used, the concept of intractability (when talking about computing problems of course) is not ...
-1
votes
0answers
14 views

How best to measure the performance of Constraint Satisfaction Problem solving algorithms?

Measuring with the time complexity is the best way to measure with CSPs algorithms or not?Which way suits the best to measure CSPs algorithms?
2
votes
1answer
34 views

What are elementary operations in time complexity definition?

Wikipedia gives us the following defintion of time complexity: "In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an ...
3
votes
1answer
36 views

Lower Bound for Time Complexity of Pairing Problem

Given an array X and array Y both of length n, the pairing algorithm will return the elements of the arrays matched so that the smallest element in X will be matched with the smallest element of Y, ...
4
votes
1answer
29 views

Graph ordering with smallest max vertex “discrepancy”

Consider an undirected graph $G=(V,E)$ and a bijective function $f:V \rightarrow [|V|]$ which orders the vertices by mapping them onto the first $|V|$ natural numbers. Define the cost of an ordering ...
1
vote
1answer
37 views

Description for languages that can be solved in time(n)?

How can one describe all languages that are in $\mathrm{TIME}(n)$? It can't be all the regular languages only, as for example $L = \{a^n b^nw \mid w \in \Sigma^* \land n \geq 1\}$ is not regular but ...
3
votes
1answer
39 views

Pebble game lower bound?

This paper says pebble games have super linear lower bound for every fixed $k$ https://dl.acm.org/citation.cfm?doid=62.322433. Why is it not considered proof of constructive example for a function in ...
3
votes
5answers
114 views

Given a set of numbers, get the maximum 10 number average below a certain threshold

As an input, my program accepts a big set of numbers (often times more than 30) and a maximum threshold. I'm trying to get the maximum average between 10 of those numbers below that threshold (the ...
0
votes
0answers
9 views

Shortcuts/Patterns for being able to calculate the running time of a loop/algorithm? [duplicate]

This is my first question here. I, like many people, suffer from the lack of the ability to be able to determine the running time of algorithms just by looking at them. I've picked up on a few ...
3
votes
0answers
22 views

Complexity of “Fast Poisson Disk Sampling in Arbitrary Dimensions”

I came across the paper Fast Poisson Disk Sampling in Arbitrary Dimensions which gives an algorithm for generating Poisson disk points in $\mathbb{R}^n$. It's claimed that the algorithm is linear ...
0
votes
2answers
26 views

Karp-Rabin - what is the input for the worst case time complexity?

I'm trying to determine the input for the worst case time complexity of Karb-Rabin regardless of the used hash function. However, I'm seeing both of these answers on the Internet: String "AAAAAAAA" ...
2
votes
0answers
24 views

Linear order minimizing weighted distance from special element

Let's say I have a set of beads, $b_0,\dots,b_n$, and let $b_0$ be the 'special bead'. I want to lay out the beads on a string to minimize the total cost, defined as $\sum_{i=1}^n w_i \cdot d(b_0, b_i)...
1
vote
2answers
94 views

Reduce 4-SAT to 5-SAT

given is a reduction from 4-SAT to 5-SAT. How is it possible to describe such a function? I found some informations about reduction 3-SAT to 4-SAT here, but it can't help me so much.
18
votes
4answers
5k views

Time complexity of an algorithm: Is it important to state the base of the logarithm?

Since there is only a constant between bases of logarithms, isn't it just alright to write $f(n) = \Omega(\log{n})$, as opposed to $\Omega(\log_2{n})$, or whatever the base might be?
2
votes
2answers
41 views

Copying items in arrays while checking their indexes

Array $P$ of length $n$ is a permutations of $\{0, ..., n-1\}$ Write a code, which would in $O(n)$ create an array $R$ of length $n$, so for values $x_i, x_j \in P$, $R[x_i] < R[x_j]$ if $...
3
votes
2answers
96 views

Bubble Sort with “while” loop - why is average case n^2?

If Bubble Sort is written as: ...
2
votes
1answer
37 views

Running time for Breadth-First-Search vs Depth-First-Search

Can someone explain why BFS is $O(V + E)$ whereas DFS is $\Theta(V + E)$. I understand the definitions of both notations, but I just don't see why the bound for DFS should be tighter than that of BFS. ...
0
votes
1answer
34 views

Quick sort worst case complexity improvement [closed]

Can the worst case time complexity of quick sort be changed from $O(n^2)$ to $O(n\log n)$ by modifying it?
1
vote
1answer
93 views

Proving recursion depth of merge sort

Hello I want to prove the recursion depth of merge sort, which is $O(\log(n))$. I think I can prove this by recurrence equation and the master theorem: $T(N)=2 T(n/2)+O(N) $ however i need to get $O(\...
2
votes
1answer
36 views

k-enclosing rectangle in two-colored point set

I was asked to write an algorithm for the following problem, and discuss complexity: There are p points of two colours, black and white, in an n*m grid. Any cell in the grid can contain 0 or ...
0
votes
0answers
16 views

What is the time complexity of FC_MRV algorithm?

I am studying CSP and read the papers on it.I wanted to know the time complexity of Forward checking with Minium Remaining Value algorithm.