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
12
votes
3answers
4k views

How fast can we find all Four-Square combinations that sum to N?

A question was asked at Stack Overflow here: Given an integer $N$, print out all possible combinations of integer values of $A,B,C$ and $D$ which solve the equation $A^2+B^2+C^2+D^2 = N$. This ...
3
votes
2answers
44 views

All possible sum of each array combination

Is there a name for this algorithm? I have an array {1,2,3} and all my possible sums are {1},{2},{3},{1+2},{1+3},{2+3}, {1+2+3} = {1},{2},{3},{4},{5},{6} {1,1,2} => {1}, {2}, {3}, {4} I tried to ...
-3
votes
0answers
32 views

OptFloodMax algorithms

For the OptFloodMax algorithm, either prove a smaller upper bound than O(n^3) on the number of messages or exhibit a class of digraphs and cot-responding UID assignments in which the ...
0
votes
2answers
182 views

Proving complexity of $T(n)=2T(n/3 + 1) + n$ non-Akra-Bazzi

We know that the complexity of $T(n)=2T(n/3 + 1) + n$ is $\Theta(n)$, as has been proved on this exchange before. However, what about proving it inductively? I believe that this method might work. ...
0
votes
1answer
12 views

A high-level call-by-reference question

First, let $H$ be a graph represented as an array of adjacency lists say. Next, let FindDegree$(H,y)$ be a standard subroutine that takes $H$ and a vertex $y$ in $H$ as input, and that returns the ...
0
votes
1answer
17 views

Complexity of insertion into a linked list, single vs double

At https://www.javatpoint.com/singly-linked-list-vs-doubly-linked-list, it says: In a singly linked list, the time complexity for inserting and deleting an element from the list is O(n). And: In a ...
2
votes
0answers
14 views

UCYCLE in LOGSPACE and linear time

Consider UCYCLE, the problem of recognizing undirected graphs containing a cycle. On the one hand, it's in LOGSPACE, see this stackexchange thread: start at every vertex $v$ a DFS and check whether it ...
0
votes
0answers
17 views

Check whether a points falls inside a rectangular in the plane

There are two points in the plane, say $p_1,p_2$. Another point $c$ is given too. The question is to determine whether $c$ fall inside the x-axis aligned rectangular whose diameter is line segment $...
-3
votes
0answers
29 views

Time complexity of assignment problem arbitrarily vs with repetition

what is the difference between the worst case time complexity of assignment problem using Hungarian method arbitrarily: choose only one optimal solution (is polynomial time)and with repetition: choose ...
-3
votes
0answers
14 views

Time complexity analysis of shannon-feno and huffman coding technique

what is the worst case analysis of Huffman coding and Shannon–Fano coding in generalized form is any better explanation plz suggest me.
0
votes
2answers
36 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 ...
2
votes
2answers
167 views

How to estimate the average time complexity of greatest common divisor?

As we know, the time complexity of $\gcd(x,y)$ is $O(\log \min(x,y))$ by using Euclidean algorithm. Now we fix a constant $n$ and consider the average time complexity of $\gcd(x,n)$. Formally, let $f(...
1
vote
1answer
17 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
1answer
98 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 ...
0
votes
2answers
20 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
60 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
21 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
26 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
13 views
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
29 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 ...
1
vote
1answer
72 views

Given $n$ unique items and an $m^{th}$ normalised value, compute $m^{th}$ permutation without factorial expansion

We know that the number of permutations possible for $n$ unique items is $n!$. We can uniquely label each permutation with a number from $0$ to $(n!-1)$. Suppose if $n=4$, the possible permutations ...
2
votes
4answers
187 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 ...
1
vote
1answer
42 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
8
votes
2answers
983 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 ...
1
vote
1answer
2k views

Calculator for time complexity of recursive functions

Is there an online tool that returns the time complexity of recursion functions? For instance, when I enter $T(n) = T(n/2) + n$, I'd like to get $\Theta(n)$. I tried using Wolfram Alpha, but it doesn'...
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, $...
0
votes
1answer
39 views

Best algorithm for Decisional 4-XOR problem?

Decisional 4-XOR Problem: Assume $M>>n$ (e.g. $M=50n$ ). Let $A_1,A_2,A_3,A_4$ be sets consisting of $M$-bit elements. Each set has order exactly $2^n$. Decide whether or not there exists $a_i \...
0
votes
1answer
51 views

asymptotic tight bounds for quadratic functions

In Introduction to Algorithms by CLRS, it's said For any quadratic function $f(n)=an^2+bn+c$, where $a$, $b$ and $c$ are constants and $a>0$, $f(n)=\Theta (n^2).$ Formally, to show the same thing, ...
0
votes
1answer
33 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. ...
0
votes
2answers
35 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
1k views

Time complexity of quicksort for arrays in increasing or descreasing order

Two $n$-size arays are given: $n_1$ is in decreasing order and $n_2$ is in increasing order. Let $c_1$ be the time complexity for $n_1$ using quicksort, and $c_2$ the time complexity for $n_2$ using ...
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
27 views

How can I develop an algorithm to schedule production?

Given an an table that contains products I am selling with the dates, and given a table that contains the possible work orders with each work order, arrange the work orders such that all items are ...
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 ...
0
votes
1answer
25 views

What are the guidelines/tips for calculating the complexity of a chained-recursive function?

Any help will be appreciated, as I wasn't able to find much about it online in the last few days and I can't seem to write a suitable recurrence relation for this kind of functions.. Are there any ...
1
vote
0answers
25 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(...
1
vote
1answer
33 views

Determine the time complexity of this algoritm (pseudocode)

{ t <- n while t>1 do t <- log_2(t) } I tried to do it this way: $f^\text{(1)}(t)=\log_2(t) \\ f^\text{(2)}(t)=\log_2\log_2(t) = \log_2^{(2)}(t) \\f^\...
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
19 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)$, ...
0
votes
1answer
34 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
0answers
27 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 ...

1
2 3 4 5
44