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
1 vote
0 answers
5 views

Proving the language 2-SIMPLE-PATH is in NL

The Question I define the language$$\mathsf{2-SIMPLE-PATH}=\left\{ \left\langle G,s,t\right\rangle \left|\begin{array}{c} \mathsf{there\;are\;two\;different}\\ \mathsf{simple\;paths\;from}\;s\;\...
0 votes
2 answers
37 views

How to find the standard theta notation of this?

Hi i am practising standard theta notation: How could i find the standard theta notation of the following : 2n + 3n^2(log n)^3 + 2 and ...
  • 3
2 votes
1 answer
16 views

Finding general time complexity for recurrence relation $T(n)=aT(n/\alpha)+bT(\beta n/\alpha)+f(n)$

I was given an assignment in which I had multiple recurrence relations and I had to find their Big-oh time complexities. Nearly all of the recurrence relations were of the form as under: $$T(n)=aT(n/\...
4 votes
1 answer
70 views

Possibly Tractable Variation of Suguru Puzzles

I'm currently investigating the computational complexity of a modified one-dimensional Suguru puzzle. The general Suguru puzzles were recently proven to be NP-complete (see here). My investigation ...
0 votes
1 answer
50 views

Time complexity of T(n) = 1600T(n/4) + n!

I'm trying to find the time complexity of T(n) = 1600T(n/4) + n! . So far I have thought of changing n! to something usable by the master theorem. Stirling's approximation gives us the equation $$\...
0 votes
1 answer
49 views

Finding the length of the longest palindrome in the given array

The problem that I'm trying to solve is: Given an array of length N, I want to find the length of the longest palindrome in the given array. With palindrome, we refer to a word, phrase, or sequence ...
0 votes
1 answer
34 views

O(nlogn)-time complexity

Is there a $O(nlogn)$ time algorithm for computing $p(x)=\sum\limits_{i=0}^na_ix^i$ ? I think with the method below I get O(n), but I need O(nlogn) Hint: there's a way to calculate $x^i$ more ...
  • 3
0 votes
1 answer
17 views

Are there any other language classes of time complexity between the P language class and the NP language class?

$P$ is the language class that is decidable in polynomial time by a deterministic Turing machine. $NP$ is a language class that is decidable in polynomial time by non-deterministic Turing machines and ...
  • 183
2 votes
1 answer
22 views

Whether the class of languages with time complexity between polynomial and exponential is an NP language?

We know that the P language class is a polynomial-time solvable language class, and the NP language class can be determined in exponential time. And there exist some languages that can be decided only ...
  • 183
0 votes
0 answers
17 views

Is there any upper bound for the number of ways we can partition a multiset, where each part/segment in the partition has distinct elements?

A question is asked in the below link, which asks for the number of cases we can partition a multiset, where each part/segment in the partition has distinct elements. https://math.stackexchange.com/...
  • 1
-1 votes
2 answers
36 views

How to prove this because if we consider big-oh than logn^2 <= log n + 5 can never happen if n grows?

f(n) = log n^2; g(n) = log n + 5 => f(n) = Θ (g(n)) I think we can prove this for omega but how can we prove it for Big oh ? because if we simplify it to logn + logn <= logn +5 => logn<=...
0 votes
0 answers
41 views

Basic Clique Complexity Question

A question in a textbook says, suppose the regular Clique problem, which takes as input a graph G and a natural number k, and returns whether or not G has a clique of size >= k, can be decided in ...
0 votes
1 answer
45 views

Is there a way to make a implication graph of the following expression?

Is there a way to make implication graph of expression of form : $$ ((x_1 \lor x_2)\lor(x_3 \lor x_2))\land(x_3 \lor x_4)$$ I haven't been able to find any sort of text on this and the usual way to ...
  • 37
0 votes
1 answer
40 views

Time complexity of $\mathsf{NP}$ problem under assumption of $\mathsf{P} \neq \mathsf{NP}$

A simple question, but I can't find an answer in quite the form I'm looking for: Assume $\mathsf{P} \neq \mathsf{NP}$, and thus $\mathsf{P} \subsetneq \mathsf{NP}$. If we have $L \in \mathsf{NP}$ and $...
  • 3
1 vote
1 answer
63 views

Another Game Theory Problem

We have an array of integers of length N(even). A and B play a game where A selects a number followed by B without replacement until the array becomes empty(Both A and B select N/2 elements each). The ...
-1 votes
0 answers
46 views

Sorting algorithm for patterns values

I have e large array of integers that contains a lot of patterns of values. A part of the array is this one, with 136, 545, 23 being repeated: [151, 42, 136, 545, 23, 8, 19, 52, 263, 68, 322, 172, 64,...
  • 1
0 votes
0 answers
23 views

Optimal time complexity to solve "maximum points on line"

Given n points on the plane, it is a standard interview problem to find the line with the maximum points, which can be done in O(n^2) with pivoting + hashmaps or other method. Question: Are there more ...
  • 101
-2 votes
2 answers
119 views

Modified Bubble Sort's time complexity

I have an array (of hundreds of numbers) and I need to sort them. In this case, I used Bubble Sort because of the better time complexity compared to other algorithms, $\Theta(n^2)$. ...
0 votes
1 answer
27 views

Algorithm Asymptotic Analysis

I'm trying to solve this time complexity: 𝑇(𝑛)=2𝑇(𝑛−2)+𝑛 but having some challenges addressing the (-2) component. Any insights on this complexity? Ended up with a section [2^2(1) + 2^(3)(2) + 2^(...
  • 1
-1 votes
2 answers
35 views

If we find that, e.g., T(n)<=d*n*lg(n) for some d that depends on n, is T(n)=o(nlgn)?

In the substitution method, if we find that, for instance, T(n) < dnlg(n) but only for some d that depends on n, then can we say that T(n) = o(nlg(n)) (little-oh) in some cases? For example, in ...
8 votes
5 answers
2k views

In algorithms for matrix multiplication (eg Strassen), why do we say n is equal to the number of rows and not the number of elements in both matrices?

In Strassen's algorithm, we calculate the time complexity based on n being the number of rows of the square matrix. Why don't we take n to be the total number of entries in the matrices (so if we were ...
0 votes
0 answers
25 views

Are all languages determined in exponential time NP languages?

According to the theorem, if $L \in NP$, then $L$ can be determined by a deterministic Turing machine in exponential time. So, are all languages determined in exponential time NP languages?
  • 183
-1 votes
0 answers
15 views

Complexity of the tau-leap algorithm

I need help estimating the complexity of the tau-leap algorithm: Equation (7) can be calculated in a constant time. My estimation the complexity of the algorithm would be O(n), where n is a number of ...
  • 1
0 votes
1 answer
35 views

Prove that $coNP \neq NTIME(n^2)$

I need to prove that $coNP \neq NTIME(n^2)$ using time hierarchy theorem. as we know $DTIME(n^4)\subseteq P\subseteq coNP$ from time hierarchy theorem we can derive that $DTIME(n^4) \not \subseteq ...
  • 1
1 vote
1 answer
54 views

What is the time complexity of removing among $N$ sets of size at most $n$ the sets which are subsets of another set?

A naïve solution would be to first sort all sets, taking time $O(N n \log n)$. Then, for every possible pair of sets, check if one is a subset of the other, and if applicable remove the subset. This ...
-4 votes
0 answers
26 views

Prove that the language $ALMOSTSC$ is $NL$-complete

Prove that the language $ALMOSTSC$ $=$ $\{$$G$ | $G$ is an oriented graph which becomes strongly connected after adding one edge$\}$ $(a)$ lies in $NL$ and $(b)$ is $NL$-complete. I'm making a problem-...
  • 1
-3 votes
0 answers
19 views

Classify the language $UNIVERSALCLIQUE$ in polynomial hierarchy

Classify the language $UNIVERSALCLIQUE$ = $\{$$(G, V_1, V_2, k, l)$ | $G = (V, E)$ is undirected graph, $V = V_1\sqcup V_2$, and some clique of $k$ vertices in graph $G_1$ together with any clique of $...
  • 1
-4 votes
1 answer
34 views

Data Structure And Algorithm

Given any singly linked-list L storing n real keys, that is, each key in L belongs to R, design an algorithm (either in words or in pseudocode) that computes the sum of the negative keys in L. What is ...
  • 1
-4 votes
0 answers
18 views

Prove that the language TWOCYCLESPERMUT lies in $L$

Prove that the language $TWOCYCLESPERMUT$ = $\{$$σ$ | in the partition of permutation $σ$ into cycles there are exactly $2$ cycles$\}$ lies in $L$. (The permutation is represented as a list of $n$ ...
  • 1
-1 votes
0 answers
18 views

Prove that language DuplBit is in coRP

Let $A ⊂ {0, 1}^∗$ and $A ∈ coRP$. Prove that the language $DuplBit(A)$ consisting of all the results of doubling one bits in some word from $A$, also lies in $coRP$.
  • 1
-2 votes
0 answers
34 views

Prove that language is in $NC$

Prove that the language CYCLE = $\{$$A$ | oriented graph with adjacency matrix $A$ contains oriented loop$\}$ lies in $NC$. Specify as precisely as possible the class $NC^k$ or $AC^k$ to which it ...
0 votes
0 answers
19 views

Order of time complexity in computing $R\sin(2\alpha)$ VS $2R\sin(\alpha)\cos(\alpha)$

I was wondering, in terms of complexity and "precision", what are the differences, if any, netween the computation of $$2R \sin(\alpha)\cos(\alpha) \qquad \qquad \text{and} \qquad \qquad R\...
  • 101
1 vote
2 answers
86 views

Perfect ordered hash function on ordered sequence

I have a sequence of integer tuples $t_1, t_2,..., t_N$ of different sizes in lexicographic order, e.g.: $(1, 1), (1, 2), (1, 3, 5), (1, 3, 6), (1, 5), (3), (3, 2, 3), (3, 7), (3, 8, 1), ...$ ...
0 votes
1 answer
40 views

Which definition of decidable is correct?

Please note I don't use any of the "verifier" notation, I only concern definitions made with DTM and NTM . Now there are two definitions of decidability: 1. A set (predicate) is decidable (...
  • 3
0 votes
2 answers
31 views

Function / Algorithm that take fixed time to compute

I was wondering if there are any mathematical functions or algorithms that take a known minimum amount of time to calculate. The closest thing I could find to this is Proof of Work algorithms used for ...
-3 votes
1 answer
38 views

How $log((mn^2)!) = \theta (mn^2 log(mn))$?

Knowing that $log(n!) = \theta(nlogn)$
0 votes
1 answer
24 views

Algorithms that depend on expected time and "regular" time complexities

Assume that I have designed an algorithm A, which runs two sub-methods: M1 and M2. M1 has a O($n$) expected time complexity. M2 has a O($n^2$) time complexity. Clearly A uses O($n + n^2$) = O($n^2$) ...
3 votes
2 answers
79 views

Complexity of taking recursive modulo

Given 2 integer $M$ and $N$, a recursive modulo is $M \bmod (M \bmod (M \bmod ...(M \bmod N)$ until the result is 0. What is its time complexity? I guess that it's $O(log(M))$ but I can't prove it.
0 votes
2 answers
155 views

Finding the time complexity of a prime factorization algorithm

In this question, I'm going to introduce a prime factorization algorithm which I'm working on as my personal project. I may attach a Python code to introduce the algorithm. If it contravenes the rule ...
0 votes
1 answer
35 views

Does it make sense to apply path compression to kruskal algorithm?

I am reading about Kruskal and analysing it’s time complexity. Let’s say there are E edges and V vertices. Kruskal algorithm has two important time complexity equations , Sort edges- Elog(E) For ...
0 votes
3 answers
65 views

Size and height of binary tree, different interpretations?

I can't seem to get my head around the formulas to use for size of binary tree. Depending on who I ask, what website, etc. I see different similar answers. So if someone could explain simply either: ...
0 votes
2 answers
39 views

Derive complexity from recurrence relation

On the Wikipedia article on Karatsuba algorithm (https://en.wikipedia.org/wiki/Karatsuba_algorithm#Time_complexity_analysis) it is stated: $T(n) = 3 T(\frac{n}{2}) + cn + d$ And then, by invocation of ...
  • 131
0 votes
0 answers
31 views

In the complexity of open addressing, why it is necessary take the sum to $\infty$?

When estimating the average calculation complexity of open addressing, I found following explanation: Let $B$ be the number of backets and $N$ be the number of elements already in the hash table. The ...
  • 1
1 vote
2 answers
332 views

Ordered sequence with logarithmic insert and remove

Problem: we have a sequence of numeric values, e.g. [102, 25, 77, 17, 2, 13]. We need to implement 3 operations, each can be at most logarithmic time complexity. <...
2 votes
2 answers
42 views

Describing the set of Running Time of all Turing Machines

Consider the set of all valid Turing Machines descriptions $T_{All}$, and the set of functions that denote the real (not asymptotic) running time of Turing Machines in $T_{All}$, lets call it $R_{All}$...
  • 23
1 vote
1 answer
18 views

Difference b/w Functional and Decisional Problem's computational complexity

I am trying to understand the difference b/w functional and decisional problems. The core as I understand is this: Functional Problems: Given an input $x$ we calculate some function $f(x)=y$ over it. ...
0 votes
0 answers
12 views

Natural Problems not in P [duplicate]

From Time-Hierarchy theorem we know that there are problems that are not solvable in polynomial time. But I would like to know some natural problems that are provably not in P. Does anyone know a ...
1 vote
2 answers
113 views

Producing "moves" to permute one array to another

I have 2 arrays, A and B, which each contain the same N elements, but in a different order. (A different permutation) There are also no duplicates in A and B. I'm trying to devise an algorithm which ...
2 votes
1 answer
30 views

Efficient Way to Calculate Timebased Followership

Problem A time based followship is defined as a person changing to a new job, and there is an existing employee there in the new company whom he used to work together. In this case, the old guy gets 1 ...
0 votes
0 answers
16 views

A query regarding reading input parameters vs hard-coding for TMs

Consider a Turning Machine $A_0$ that takes two input parameters $(x, y)$ and its (exact not asymtotic) (polynomial) running time is given by $f(|x|, |y|)$ such that $x^c < f(|x|, |y|) < x^{c+1}....
  • 703

1
2 3 4 5
50