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
votes
0answers
8 views

Time complexity of assignment problem arbitrarily vs with repetition

what is the difference between time complexity of assignment problem arbitrarily and with repetition?
0
votes
0answers
11 views

Solve recurrence where the base case's time complexity is a function of the original input size

I'm trying to analyse the time complexity of the following algorithm for generating the power set: ...
0
votes
2answers
17 views

Searching for sorting algorithm taking into account all possible solution of similar numbers

I need a reference for sorting algorithm where all possible orders are considered. example: if we have four values of n, and we do know there values n1(3) n2(5) n3(5) n4(10) and want to order them in ...
0
votes
1answer
44 views

How to determine if a tree $T = (V, E)$ has a perfect matching in $O(|V| + |E|)$ time

This is a problem I've come across while studying on my own; it's from Algorithms by Papadimitriou, Dasgupta and Vazirani. Specifically, the problem statement is: Give a linear-time algorithm that ...
0
votes
0answers
13 views

Parameterized complexity of 3-SAT

Is the 3-SAT problem with $s$ variables and $t$ clauses FPT, parameterized by $s+t$, or W[1]-hard, or para-NP-hard?
-2
votes
1answer
24 views

Need the time complexity of this conditional statement method

My idea of the program is : Input = n sets objective function ObjFn equals to O(n^3) Output = the order of n sets Steps: Applying ObjFn to all n sets Choose the n of the Minimum ObjFn to be ordered ...
0
votes
0answers
20 views

what is the running time of this while loop? [duplicate]

Hello i have a piece of code like this: ...
0
votes
0answers
23 views

Intuition behind : recursive algorithm takes exponential time [duplicate]

So I am studying an introductory chapter to dynamic programming that suggests a general solution to an optimization problem that occurs straightforwardly from expressing the problem with a reccurence ...
-3
votes
0answers
13 views

recurrence equation 2T(n-4) + n^2 solution?

need help solving this equation. the general equation I end up with: 2^k * 2T(n-4k) + [ 2^k-1(n-4(k-1))^2 + 2^k-2(n-4(k-2))^2 + 2^k-3(n-4(k-3))^2....2^k-k(n-4(k-k))^2 ]
-1
votes
0answers
22 views

Can a machine that, given infinite space, functions as a non deterministic turing machine actually exist in the real world?

I am a novice when it comes to computer science. But I know that traditional quantum computers are not non deterministic Turing machines. But it seems to me that the principles of quantum mechanics ...
0
votes
0answers
13 views

Relation between time complexity and conditional statement [closed]

I need examples for the types of time complexity for conditional statement
1
vote
1answer
41 views

What is the big-$O$ notation of a summation of logs where the arguments add to $n$?

For: $$\sum^{k}_{i=1} \log(x_i)$$ where: $$\sum^{k}_{i=1} x_i = n$$ Is there any big-$O$ result in terms of $n$ ? I found this, but is not what I'm looking for.
-4
votes
0answers
17 views

What's the big O notation of this function and can you please explain why?

void RandIntArray(int arr[], int n) { int i, first, second, temp; ...
0
votes
1answer
32 views

References to deterministic time complexity of language classes

It's fairly well known that $REG \in TIME(n)$. I would like to know similar inclusions for the language classes $DCFL$ and $CFL$. I have found a variety of claims for these classes on the internet. ...
2
votes
4answers
125 views

Find two non-overlaping subarrays, with total sum equal to k

Given an array of N non-negative integers, and a number K, we need to find two non-overlapping contiguous subarrays that have a total sum of K. Our algorithm is supposed to find the minimum total ...
0
votes
2answers
34 views

Regularity condition for cases 1 & 2

My question concerns the version of the Master Theorem described in CLRS and in this handout. I already understand the following: If the regularity condition in case 3 does not hold, then we can't ...
0
votes
1answer
9 views

What is the time complexity of a Turing Machine that iterates through each prime number from 2 to K (assume oracle generates the next prime)?

Let NextPrimeNumber be an oracle that accepts a prime number n and returns the smallest prime number ...
0
votes
1answer
23 views

Hashing using chaining

In resolving collisions while hashing by chaining , if we store keys in the list in sorted manner, will we obtain any substantial performance in successful searches , insertion, deletion? What would ...
0
votes
1answer
21 views

polynomial time approximation algorithm problem

How can we actually define a polynomial-time 4-approximation algorithm for vertex cover or knapsack problem? For say we have 2 approximation problems which less than equal 2C*. But when we have a ...
1
vote
0answers
24 views

Adversary argument and proving a lower bound of an algorithm. How does it work?

I need to understand how adversary argument works to prove the lower bound of an algorithm. For now, I am looking to prove that a "certain" algorithm that takes in input array requires omega(...
0
votes
0answers
25 views

Symmetry group of the acyclic oriented L-cube using the Hyperoctahedral group

I'm trying to figure out all elements of a symmetry group for the acyclic oriented $L$-cube. I do have an algorithm, but its complexity is not suitable for larger $L$. I computed $L=5$ on my old ...
1
vote
1answer
14 views

Efficient intersection detection between disks with identical radius

I have a set of $N$ points randomly positionned on a rectangular space (btw with either absorbing, reflecting or wrapping boundaries), and I need to obtain the distances between every 2 points whose ...
0
votes
3answers
30 views

For 3CNF unsatisfiable boolean formulas, does it take exponential time to transform them into disjunctive form?

From the link Solving SAT by converting to disjunctive normal form, I learnt that the algorithm to transform any boolean formula to disjunctive form takes exponential time in worst case. But I have a ...
1
vote
1answer
40 views

Average case complexity and Big-O

In this Wikipedia article on Average-case complexity there is the text: For example, many sorting algorithms which utilize randomness, such as Quicksort, have a worst-case running time of $O(n^2)$, ...
1
vote
0answers
26 views

Algorithm better than O(nlgn) for josephus problem to print killed person in order

My problem base on the josephus problem, I want to print the position of killed people one by one in order. People are standing in a circle waiting to be executed. Counting begins at a specified ...
-3
votes
0answers
14 views

Bubble Sort Runtime complexity analysis l [duplicate]

I'm trying to find the time complexity of this cod line by line can you help me?
0
votes
1answer
33 views

Quicksort with insertion sort

Okay so I have implemented quicksort with insertion, where K is a value until which the recursion occurs and then rest of the array is sorted using insertion sort. Now I am comaparing 3 different ...
1
vote
1answer
39 views

Time Complexity Sigma Notation

Consider the following pseudo-code: counter = 0 for (k = 16; k > 0; k /= 2) for (j = 0; j < k; j++) counter++ I get that the time complexity is $...
1
vote
1answer
58 views

Complexity difference of Vertex cover and Vertex coloring regarding parametrized algorithms

I stumbled upon some problem in my understanding of the complexity classes FPT and XP. According to Wikipedia (and the Book "Parameterized Algorithms") we know the following about the Vertex ...
1
vote
1answer
17 views

Karatsube-Ofman runtime complexity computation

I have a question and didn't understand the solution, since we didn't take how to do it in the lecture and it's not explained in the solution sample. Question: One can generalize the Karatsube-Ofman ...
0
votes
1answer
20 views

Insertion Sort running time calculating using summtion

I was reading Introduction to algorithms, and stopped at the calculating the running time. For each $j = 2,3,..,n$ where $n = A.length$, we let $t_j$ denote the number of times the while loop test in ...
0
votes
1answer
31 views

Time complexity when loop index is an exponent

For any $n$ and any $x$, if one implements a loop to calculate: $$\sum_{i=0}^n x^i$$ What is time complexity of said loop if we assume $x^i$ to have time complexity of $O(i)$? What confuses me is the ...
-3
votes
0answers
32 views
0
votes
1answer
22 views

A query regarding Complexity class BPP and NP

It is known that: $\Sigma_2^P \subseteq \Delta_3^P$ i.e. $NP^{NP} \subseteq \Delta_3^P$. $BPP^{NP} \subseteq \Delta_3^P$ If $\Sigma_2^P = PSPACE => BPP^{NP} \subseteq NP^{NP}$ Doesn't that imply: ...
2
votes
1answer
53 views

Prove by induction $T(n) = T(\lfloor\frac{n}{2}\rfloor)+n^2 \in \Theta (\log_2 n)$

Text of the problem: Solve the following recurrence equation and prove it by applying the principle of induction: $T(n) = \begin{cases} 3, \ n \le 2 \\ T(\lfloor\frac{n}{2}\rfloor)+n^2, \ n \ge 3 \...
1
vote
0answers
21 views

Solve the K_ELEMENT problem using INTERSECT

Suppose you have a machine that takes inputs a set of sets, $\{S_1,S_2,\dots S_n\}$, and an integer $k$. The machine then returns True if $S_1$ intersects every ...
2
votes
1answer
25 views

Intuitive understanding of the Boolean Hierarchy

I am trying to understand the Boolean Hierarchy. the formal definition of the Boolean Hierarchy is as follows: $BH_1 = NP$ $BH_{2k}$ is the class of languages which are the intersection of a ...
0
votes
1answer
48 views

Compare growth rate two functions

Suppose $f_1(n)=n\log^*n$,$f_2(n)=n\log h$ that $h$ is number of vertices of convex hull. Can we conclude that $$f_1+f_2=O(f_2)?$$ Edited: Note that, $h$ is a function accroding to $n$ that $h\leq n$, ...
0
votes
1answer
19 views

Find an integer such that linear equation becomes divisible by another given integer

Given integers a, b, and c all <=n, is there an efficient algorithm to find an integer y such that a | c + b*y? One brute force approach will be to check for all y = 0 to n and if there is a ...
0
votes
2answers
31 views

Complexity of calculating sin(nx)

Suppose we are give a natural number $n$, the value of $\sin(x)$ and $\cos(x)$. How efficiently can we compute $\sin(n x)$? My Thoughts : The $\sin (n x)$ expansion will have $O(n)$ terms. The power ...
1
vote
1answer
16 views

A query regarding the definition of Polynomial Hierarchy and PSPACE

If a $\mathsf{PSPACE-Complete}$ problem (say $\mathsf{TQBF}$) has an algorithm that has the runtime $\mathsf{NP^{NP}}$ it follows that $\mathsf{PSPACE=\Sigma^P_2}$. Does that also imply $\mathsf{\...
1
vote
1answer
53 views

Expected linear-time algorithm for finding MST with probability for sampling an edge other than 1/2

I'm trying to understand this algorithm : https://en.m.wikipedia.org/wiki/Expected_linear_time_MST_algorithm As described in the wiki article, it works in 5 steps to find the MSF for a graph $G = (V, ...
2
votes
0answers
24 views

Fast calculations using fast-Fourier convolution

Consider an array $X$ with shape $H \times W$. Let $Y$ be the other array of the same shape and $Z$ is an array of shape $h \times w$. We want to construct an array $R$ of shape $(H-h + 1, W-w+ 1)$ by ...
0
votes
0answers
27 views

Check if the given satisfying assignment of CNF formula is lexicographically the first

If there is a CNF Boolean formula in $n$ variables then the potential satisfying assignments are the binary strings of length $n$. Given a CNF Boolean formula and a satisfying assignment how ...
0
votes
1answer
36 views

Computational Complexity of an 'equivalent' 3SAT instance problem

Given a random $3SAT$ instance $(S_0)$ with $C_0$ clauses, $I_0$ variables. Objective: For any given value $C_1$ ($C_1<C_0$), create an 'equivalent' $3SAT$ instance $(S_1)$ with $I_0$ variables, $...
-1
votes
1answer
56 views

Quasilinear time algorithm for 3-SAT

Is it consistent with the current knowledge that there is an algorithm solving a 3-SAT instance in $n$ clauses in quasilinear time in $n$?
-1
votes
1answer
43 views

what is the time complexity of this for for for if

I need to know the analysis of time complexity of this case? ...
0
votes
1answer
278 views

Best algorithm to find "deepest" interval

Let's say I have a list of intervals on a number line. The "depth" of a point on this number line corresponds to the number of intervals in the list that contain it [the point]. So for ...

1
2 3 4 5
44