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
3answers
147 views

Time complexity - Algorithm to find the lowest common ancestor of all deepest leaves

This is the problem statement I came across today. Given a binary tree, find the lowest common ancestor of all deepest leaves. I came up with a correct algorithm, but I would like to confirm the ...
1
vote
0answers
30 views

Time complexity of a hybrid merge and selection sort algorithm

I'm trying to analyse the time and space complexity of the following algorithm, which is essentially a hybrid of a merge and selection sort. The algorithm is defined as follows: ...
0
votes
0answers
40 views

What can be said about complexity class of a problem if there exist a pseudo-polynomial verification algorithm?

Let X be a problem for which pseudo-polynomial algorithm time for verification of solution exists. What can be said about complexity of problem X? Can X belong to NP-hard class?
1
vote
1answer
39 views

Runtime of weighted interval scheduling dynamic programming algorithm

Consider this implementation of a dynamic programming algorithm for weighted interval scheduling: ...
2
votes
0answers
27 views

Can every node of a link/cut tree be accessed in $O(n)$ time?

Per the Sequential Access Theorem we can access every node of a splay tree in $O(n)$ time, when accessing the nodes in a specific order. Given a link/cut tree, is it possible to access all of its ...
3
votes
2answers
76 views

Why is $O(|V| + |E|)$ the bound on DFS and BFS instead of just $O(|E|)$?

In one sense I understand why the bound on BFS and DFS is $O(|V| + |E|)$. Every vertex gets considered, hence the $O(|V|)$, and over the course of considering all adjacent vertices, we end up ...
0
votes
1answer
28 views

Uniqueness of non-dominated two-dimensional points

This question is a nice variant of How to compare n number of m-dimensional points among one another with minimum time complexity? for two dimensions. We say point $p_i=(x^i_1, x^i_2)$ dominates ...
2
votes
1answer
55 views

NP-completeness of a problem with pretty fast algorithm

Supposing if a problem with $n$ non-deterministic bits is in $O(2^{\alpha n})$ time at every $\alpha\in(0,1)$ then is there evidence that problem can or cannot be $\mathsf{NP}$-complete?
3
votes
0answers
22 views

Bit complexity of computing the sign of an expression evaluated at an algebraic number

I have a univariate polynomial $F(t)\in \mathbb{Z}[t]$ of degree $d$ and maximum bitsize of coefficients equal to $\tau$ and $G(t) \in \mathbb{Z}[t]$ of degree $d^2$ and maximum bitsize of ...
1
vote
1answer
69 views

PTAS vs. FPTAS input

I am trying to understand what is the PTAS, FPTAS and what is the difference between them. I found this analysis: PTAS definition vs. FPTAS but I cannot understand what do we mean by saying: ".......
2
votes
1answer
112 views

How to compare n number of m-dimensional points among one another with minimum time complexity?

Suppose there are four points (n = 4) which are four dimensional (m = 4) . Lets say these points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4). What is the best data structure to compare all ...
2
votes
0answers
24 views

planar max cut graph with constrains

Given a planar graph $G=(V, E)$ I am looking for a max cut algorithm with the following conditions : some vertices are in one of the partition sets? Is the algo is still polynomial ? I mean a ...
2
votes
1answer
36 views

Coloring a graph with odd number of vertices with $k$ (which is close to $\Delta$) colors in linear time

We have an undirected simple connected graph with odd number of vertices. We also know the number $k$ which is actually the closest odd number greater than or equal to $\Delta$. (So if $\Delta$ is ...
0
votes
0answers
27 views

Quick Clarification Question about Time Complexity in CLRS

I'm reading about the Hiring Problem in "Introduction to Algorithms" and read Interviewing has a low cost, say $c_i$, whereas hiring is expensive, costing $c_h$. Letting $m$ be the number of ...
2
votes
1answer
37 views

What's the decoding time complexity of LT codes?

LT codes are practical fountain codes that are near-optimal erasure correcting codes. Simply stated, for encoding a $n$-block message, each packet first chooses a degree $d\in\{1,\ldots,n\}$ ...
2
votes
1answer
55 views

Time complexity of algorithm inversely proportional to size of sub problem?

Let's say I have an algorithm with time complexity $T_n = T_\frac{n-1}2 + 1$, $T_0 = 0, T_1 = 1$. Assume (Induction hypothesis) $T_n = C\log_2(n+1)$ for some $C$. $T_1$ imposes $C \geq 1$. Therefore ...
1
vote
1answer
90 views

Time complexity of combinations of n pairs of parentheses

I have the following code snippet for combinations of n pairs of parentheses. ...
3
votes
1answer
46 views

Fastest algorithm for transforming points into graph

Given a set of $n$ two-dimensional points in the plane $$\{ (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\}$$ and a real number $M$, I want to transform this set of points into a graph with the points as ...
3
votes
1answer
93 views

Comparing asymptotic running time of two algorithms $\sqrt n$ and $2^{\sqrt{\log _{2}n}}$

Given two algorithms with their time-complexity $t_a(n)=\sqrt{n}$ and $t_b(n) = 2^{\sqrt{\log _{2}n}}$ and i have to show $t_b(n) = O(t_a(n)) $. I´ve made a program to check this statement and it ...
0
votes
1answer
59 views

Time complexity of a 2-heap question

The problem statement is pretty straight forward: given an array of integers and a window size, return an array of doubles of the median of each window. arr = 1, 3, 5, 10, 6, 9, 2 k = 3 would yield ...
3
votes
1answer
121 views

Compare two complexity functions having the same asymptotic complexity

For a certain problem two solution algorithms (A1 and A2) with the following execution times have been found: $A1: T_{A1}(n)=4n^2 +7log(n^2)$ $A2: T_{A2}(n) = 4T(n/2) + log(n)$ Say, technically ...
1
vote
0answers
35 views

Which function grows faster: N Log N or N^(1+ε/√(log N)) [duplicate]

How would you go about solving this problem? I thought about using a limit infinity approach, but got confused and Wolfram Alpha didn't provide any explanation.
2
votes
1answer
71 views

Are problems in NP $\cap$ coNP less difficult than those in NP-complete?

I am taking a complexity class now, and I struggle to understand the concept of "hardness": Assume that $L \in \textsf{NP } \cap \textsf{coNP}$. In means that under the assumption $\mathsf{NP} \neq \...
-1
votes
2answers
28 views

Units of time in time analysis (frequency count method)

In time analysis, how many units of time will the piece of code z=2x+3y; take? will it take 1 unit of rime or 4 units of time ?
4
votes
1answer
108 views

Improving time complexity from O(log n/loglog n) to O((log ((nloglog n)/log n))/loglog ((nloglog n)/log n))

Suppose I have an algorithm whose running time is $O(f(n))$ where $f(n) = O\left(\frac{\log n}{\log\log n}\right)$ And suppose I can change this running time in $O(1)$ steps into $O\left(f\left(\...
0
votes
1answer
103 views

Understanding $O(2^n)$ time complexity due to recursive functions

Consider the following binary recursive fibonassi program: ...
0
votes
1answer
32 views

how to proof ${ NPC \bigcap CO-NPC \ne \varnothing then NP = P ? }$

how proof ${\ \ NPC \ \ \bigcap \ \ CO-NPC \ne \varnothing }$ then ${NP = P ? }$
0
votes
1answer
75 views

How to get Algorithm complexty based on another 2 algorithms?

I had quiz last week and it says: suppose algorithms $A_1$ and $A_2$ have worst-case time bound $p$ and $q$, respectively. Suppose algorithm $A_3$ consists of applying $A_2$ to the output of $A_1$. (...
0
votes
1answer
26 views

Partitioning a set based on binary predicate

Given a collection of objects $X = (x_0,x_1,...,x_{N-1})$ and a binary predicate $F$ which takes as parameters elements of the collection, find a better than $\mathcal{O}(N^2)$ algorithm which ...
2
votes
1answer
88 views

Assume that NP = DTIME(2^sqrt(n)), prove that DTIME(2^sqrt(n)) = DTIME(2^n)

I tried using the padding argument to prove such a thing (as it appeared in Arora's book), but I am not sure how this technique will help me here. I am trying to get to a contradiction to the Time ...
0
votes
1answer
35 views

How does $n^c \lg n, 0<c<1$ compare to other common time complexities

Between what two common time complexities would you place $n^c lg n, 0<c<1$? The following table illustrates the common time complexities. Source: wikipedia
-2
votes
1answer
35 views

please tell Time complexity of following program [closed]

please tell the time complexitiy of the following code
2
votes
1answer
78 views

Is SAT a single language or a union of languages?

I know that a language is in NP if a Turing machine can decide the language of its checking relation $\{\text{boolean formula }\#\text{ truth assignment | truth assignment is correct}\}$ in polynomial ...
1
vote
1answer
28 views

Non-deterministic Turing machine for $L_1 = \{w\#0^n|w \text{ is a suffix of some $x$ in $L$ with } |x|=n\}$

Show if L is in NP, then also L1 is in NP $$L_1 = \{w\#0^n|w \text{ is a suffix of some $x$ in $L$ with } |x|=n\}$$ I know that if L is in NP, then there exists a NTM $M_L$ than accepts $x$, ...
0
votes
1answer
44 views

Time complexity to find out the number of ways to parenthesize N matrices

I am trying to figure out the $time$ $complexity$ to find out the number of ways we can parenthesize $N$ $matrices$. I have approached this problem as, say if we have $N+1$ matrices then we can ...
2
votes
0answers
32 views

Find sub-matrix containing the maximum number of elements consisting only of 1's [closed]

I am trying to get help on it here, originally posted first at: https://stackoverflow.com/questions/59446920/find-sub-matrix-containing-the-maximum-number-of-elements-consisting-only-of-1s Basically ...
1
vote
1answer
47 views

What is $f(n)$ in $NTIME(n)\subseteq DTIME(f(n))$ if $CIRCUITSAT$ is in $P$?

If $CIRCUITSAT$ in $n$ variables and $m$ gates has an $O((nm)^c)$ algorithm for a fixed $c>0$ then $NTIME(n)\subseteq DTIME(O(f(n)))$ for large enough $f(n)$. What is the smallest $f(n)$ in $NTIME(...
2
votes
2answers
279 views

Complexity of cyclic sort

I have this algorithm ("cyclic sort") to sort an array which contains unique numbers from 1 to $n$: ...
1
vote
1answer
27 views

Arbitrary Turing machine run time analysis on the empty word

Consider $L = \{ \langle M,n \rangle : M $ accpets $\epsilon $ in less than $T(n)$ steps$\}$ This language is decidable because a decider can simulate $M$ on $\epsilon$ and accept if it accepts and ...
0
votes
1answer
183 views

How to find time complexity of this pseudocode

Recently, I came across a question about finding sum of all values in range $[low, high]$ in BST $T$. Then I formulated following algorithm to carry out that task: We do inorder traversal of ...
0
votes
0answers
30 views

Algorithm to Find $x$ and $y$ for array of $3n$ numbers such that 1/3 are less than $x$. 1/3 between $x$ and $y$ and 1/3 greater than $y$

We have An array of $3n$ elements. we want to Find $x$ and $y$ for array of $3n$ numbers such that 1/3 are less than $x$. 1/3 between $x$ and $y$ and 1/3 greater than $y$. We can solve this problem of ...
2
votes
2answers
54 views

What algorithm may be used to solve the re-assembly of shredded papers?

I was once given this question in an interview: Suppose a piece of paper has 80 columns of alphabets with a fixed size font, and now the paper is shredded vertically, into 80 vertical pieces (so ...
25
votes
2answers
4k views

Understanding of big-O massively improved when I began thinking of orders as sets. How to apply the same approach to big-Theta?

Today I revisited the topic of runtime complexity orders – big-O and big-$\Theta$. I finally fully understood what the formal definition of big-O meant but more importantly I realised that big-O ...
1
vote
0answers
55 views

Optimal ordering - Dynamic programming on subsets

We have a set T of n elements and m subsets $R_i \subset T i = 1,...,m$. The $S_i$ are not assumed to be different. We also define an ordering of T, a one-to-one mapping $\pi$ of $T$ onto the set of ...
0
votes
0answers
18 views

Proof that Special case of SUBSET SUM is in P [duplicate]

So i know that SUBSET SUM is in NP. But given the following special case: The numbers $\ a_i,...,a_n $ with $\ i= 1,...,n-1 $ fulfill the condition: $\ a_i|a_{i+1} $ ($\ a_i $ divides $\ a_{i+1} $) ...
5
votes
2answers
80 views

Does $P/O(1)$ equal to $P$ if solver needs to consider smaller inputs?

Suppose that $F$ is a problem such that for every $n$, there is a program of length $O(1)$, running in polynomial time to $n$, that solves $F$ correctly on all instances of size less than $n$. Can $F$ ...
2
votes
1answer
40 views

What is the time complexity of determining whether a solution $x$ exists to $x^k \equiv c \pmod{N}$ if we know the factorization of $N$?

Suppose we are given an integer $c$ and positive integers $k, N$, with no further assumptions on relationships between these numbers. We are also given the prime factorization of $N$. These inputs are ...
2
votes
1answer
59 views

How memory controller reads from RAM with O(1) time complexity?

I am trying to understand how a RAM memory controller gets data with instant access while reading through the memory. Let's say initially, ram gets the data at address 0 and then to get the data at ...
2
votes
1answer
134 views

Why does $L = \{ 0^n 1^n \space | \space n \in \mathbb{N} \}$ belong to $\mathrm{P}$?

My professor said that the non-regular language $L_{1} = \{ 0^n 1^n \space | \space n \in \mathbb{N} \}$ belongs to $\mathrm{P}$. I do understand that all regular languages belong to $\mathrm{P}$ as ...

1 2 3
4
5
34