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.
1,898
questions
1
vote
2answers
164 views
0
votes
3answers
180 views
Sum rule for Big-O with equal complexity-functions?
One property of the Big-O-notation is the sum rule, which states that when I have two functions $f_1$ and $f_2$ and their corresponding complexity functions are $g_1$ and $g_2$, then the combined ...
1
vote
1answer
36 views
Big-O of iterating through nested structure
While trying to understand complexity I run into an example of going through records organized in following way:
...
5
votes
4answers
1k views
Is it possible for the runtime and input size in an algorithm to be inversely related?
I'm wondering if it's possible for algorithms that have monotonically decreasing runtime with the input-size - just as a fun mental exercise. If not, is it possible to disprove this claim? I haven't ...
0
votes
1answer
38 views
Determine if there is a subset of the given set with sum divisible by a given integer
I've been given a question to solve:
Given a set of non-negative distinct integers, and a value $m$, determine if there is a subset of the given set with sum divisible by $m$.
For this question the ...
3
votes
1answer
93 views
Maximal subsets of a point set which fit in a unit disk
Suppose that there are a set $P$ of $n$ points on the plane, and let $P_1, \dots, P_k$ be distinct subsets of $P$ such that all points in $P_i$ fits inside one unit disk for all $i$, $1\le i\le k$.
...
1
vote
3answers
253 views
What complexity does this 'how many ways to climb' algorithm have?
I have a solution to the following problem:
Given a stairway of $n$ stairs, which you can climb from $1$ to $m$ at the
time ($1 \leq m \leq n$), return all the ways you can climb the stairway.
...
2
votes
2answers
103 views
Efficient way to reduce a binomial coefficient as a fraction
Here is the full problem.
You need to calculate Euler's totient function of a binomial coefficient $C_n^k$.
Input
The first line contains two integers: $n$ and $k$ $(0 \le k \le n \le 500000)$.
...
1
vote
3answers
232 views
Can you insert into sorted list with time O(1)?
Wondering if this was possible. If I have a sorted list, can I find the right spot for an integer and insert it, all in O(1) time? The only way I can think to do this is via having a MASSIVE hashmap ...
3
votes
1answer
88 views
Disprove unrealistic speed-up of total Turing machines
Let $T_1$ be a total Turing machine deciding language $L_1$, and let $I_1$ and $I_2$ be two separate inputs to $T_1$. Further, let $I_{c}$ be $I_2$ concatenated to $I_1$ with some separation symbol in ...
3
votes
3answers
95 views
Are there any examples of projects running a program that will take many years to finish its job?
There are algorithms that are said to be unfeasible to be applied in practice due to their time complexity. In textbooks, it's common to see remarks like "it would take hundreds of years" ...
0
votes
1answer
154 views
Given two identical DOM trees find same node in tree B
So for the question 'Given two identical DOM trees, and an element in one tree, find the same element in the second tree'.
I can solve it in two ways -
Start at the given element and traverse up to ...
3
votes
1answer
274 views
efficient algorithm for min cut with specified number of vertices
Consider a graph with vertices $V$ and edges $E$. The standard version of the min cut problem is to find the partition of $V$ into a (non-empty) subset $C$ and its complement $\bar{C}$ so as to ...
3
votes
3answers
175 views
What is the complexity of $i^i$?
What is the complexity of the following algorithm in Big O:
for(int i = 2; i < n; i = i^i)
{
...do somthing
}
I'm not sure if there is a valid operator to ...
0
votes
1answer
145 views
Bubble Sort: Runtime complexity analysis line by line
I'm trying to analyze Bubble Sort runtime in a method similar to how to it's done in "Introduction to Algorithms 3rd Ed" (Cormen, Leiserson, Rivest, Stein) for Insertion Sort (shown below). ...
0
votes
0answers
29 views
Time complexity about Maximum subarray
I recently came across a function called the strawman algorithm which the pseudo code looks like this:
...
2
votes
2answers
58 views
Description logics with decision problems within NP
Is there any description logic where important decision problems (e.g. abox consistency or concept satisfiability) lie within NP with respect to their time complexity?
The well-researched family of $\...
1
vote
1answer
43 views
Difficulty understanding the use of arbitrary function for the worst case running time of an algorithm
In CLRS the author said
"Technically, it is an abuse to say that the running time of insertion sort is $O(n^2)$,
since for a given $n$, the actual running time varies, depending on the particular
...
2
votes
2answers
98 views
How does f(n) < cg(n) specify time?
I have been reading this tutorial on time complexity, and I am a bit puzzled on its explanation of big $O$ notation. It writes:
$O(g(n)) = $ { $f(n)$ : there exist positive constants $c$ and $n_0$ ...
1
vote
1answer
54 views
While number can be checked for primality in O(n^0.5) then why was it considered to be not in P until AKS test?
While a basic algorithm to check for primality of a number 'n' [checking if a divides n for all a less than n] would take O(n), AKS test was the breakthrough after which it was placed in P complexity ...
0
votes
0answers
32 views
Selecting n elements from array in sublinear time and subquadratic compute and memory complexity using indices
Are GPUs or CPUs capable of selecting n elements from an array in sublinear time using indices? If so, what would be some good alternatives to achieve this?
Lets say I have an array A = {1, 5, 6, 3, 6,...
-1
votes
1answer
72 views
What is Simple Uniform Hashing, and why searching a hashtable has complexity Ī(n) in the worst case
Can anyone explain nicely what Simple Uniform Hashing is, and why searching a hashtable has complexity Ī(n) in the worst case if we donāt have uniform hashing (where n is the number of elements in the ...
-1
votes
1answer
48 views
How to know if time complexity is O(n+m) or O(n*m)
I'm having difficulty understanding when can we know if the time complexity of an algorithm is n+m or n*m
Is the time complexity of the following algo O(n+m) or O(n*m)
Can you please point me to a ...
0
votes
2answers
74 views
Big O notation, code time complexity
does appending an element to a list through a for loop work in O(1) time or O(n) time? In addition, what is the time complexity does "".join that list into a string work in?
1
vote
2answers
54 views
What is the smallest time/space complexity class that is known to contain complxity class $\mathsf{SPARSE}$
Is it known if complexity class of all sparse languages is contained within e.g. $\mathsf{EXP}$ or $\mathsf{EXPSPACE}$? Or what is the smallest time or space complexity class that contains complexity ...
0
votes
0answers
11 views
What does increasing the input size by a factor of 100 do to a linearthimic algorithm with the complexity of 2nlog(n)
So far what I've tried to do is break this into parts and work from there
So for the $2n$, increasing by a factor of 100 means the runtime goes up by 100 times
But I get stuck with the log(n) part. ...
1
vote
0answers
41 views
Complexity of find histogram bins vs convex hull
For a list of n 2d points, finding the convex hull vertex takes O(n log(n)) time. And O(n) time if itās sorted lexicon order.
Meanwhile Whatās the complexity of finding the histogram bin edges of k ...
1
vote
0answers
44 views
Complexity Values for Specific Code/Functions
(1) Assume a function $f:\mathbb{Z^+}\rightarrow\mathbb{R}$ that's defined in a way that utilizes, say, eight basic computations, including addition, subtraction, division, multiplication, (positive ...
0
votes
0answers
46 views
Reconstructing an Array via Time-Intensive Subset Queries
I am trying to design an algorithm for a problem, and the following is an auxiliary problem for which a good solution would imply a faster algorithm for the original problem.
I am given access to an ...
2
votes
0answers
41 views
How do you convert an NP problem which runs in O(f(x)) time in a SAT instance with O(f(x)*log(f(x))) variables in O(f(x)*log(f(x)))
I looked at the Cook's theorem at Wikipedia which presents a way to convert any NP problem to SAT but it seems to require O(f(x)^3) variables. Is it possible to remove some of the checks in the ...
0
votes
2answers
252 views
Is there a better-than-brute-force algorithm to generate a graph whose relation is string edit distance=1?
I'm interested in creating a graphs whose vertices are strings, and whose edges represent the relation of having an edit distance of 1 under a given string metric.
An obvious approach is to make all $...
1
vote
1answer
29 views
Relations between deciding languages and computing functions in advice machines
I'm trying to understand implications of translating between functions and languages for P/Poly complexity. I'm not sure whether the following all makes sense. Giving it my best shot given my current ...
12
votes
5answers
3k views
Efficient algorithm to compute the $n$th Fibonacci number
The $n$th Fibonacci number can be computed in linear time using the following recurrence:
...
0
votes
1answer
96 views
algorithm to find shortest path connecting EVERY node
I have received a problem to solve and I am not sure what algorithm to use.
TLDR; Find the shortest path to get to every node in a undirected graph
The problem states that one must visit every ...
0
votes
1answer
67 views
How do you calculate the running time using Big-O notatation?
I'm still new to Data Structure and Algorithm and therefore I would like to ease my doubts. I'm required to find the Big-O running time of myMethod():
...
1
vote
2answers
77 views
How to determine if given ācomplexā time complexity is $O(n^2)$?
If a given time complexity, such as these:
$(n + \log n) * \sqrt{n+\log n}$
$n * (200 + \log^2 n)$
$(7+n^3)\log(n^5)$
is not determinable by just looking at it whether is it in class $O(n^2)$ or not,...
0
votes
0answers
47 views
Calculating the running time of Quicksort's PARTITION procedure
I am confused about calculating the PARTITION procedure's running time.
PARTITION procedure is used in the Quicksort Algorithm to partition the array $A[p...r]$
I analyzed the PARTITION procedure ...
0
votes
0answers
27 views
$NP$ is not in $P(n^k)$ for any fixed $k \geq 1$
I encountered this problem which asks to show that for any fixed $k \geq 1$, $NP$ is not contained in $P(n^k)$...
As an attempt, I thought of using the time hierarchy theorem which says that there ...
-1
votes
1answer
31 views
If $j ā 1 < \log k < j$. Why is $j = O(\log k)$?
If $j \in Z^+$ and $k \in R^+$ and $j ā 1 < \log k < j$. Why is $j = O(\log k)$? (All log's are in base 2)
I know I have to find constants where $j <= c \cdot \log k$ but I need some help ...
0
votes
1answer
59 views
Why is the hitting set problem in NP
I am citing the definition of the Hitting Set Problem from (Gardy & Johnson, 1979):
INSTANCE: Collection $C$ of subsets of a set $S$, a positive integer $K$.
QUESTION: Does $S$ contains a ...
0
votes
2answers
167 views
Time complexity of printing prime numbers within a range?
I've written an answer to this question, which asks about the following:
What is the time complexity for the given code that prints prime numbers from start to <...
1
vote
1answer
233 views
How do I calculate the time complexity of this memoized algorithm?
The problem is: count all increasing subsequence of s.
...
1
vote
0answers
25 views
Finding Smallest Frontier for Graphs of bounded pathwidth
Let $G$ be a graph and $X=x_1,x_2,...,x_n$ be an permutation/ordering of the vertex set of $G$. We then let $S_i = \{x_j:j\le i\}$, and $F_i$ be the number vertices $v\in S_i$ that are adjacent to ...
0
votes
1answer
114 views
Worst Case for AVL Tree Balancing after Deletion
After deleting a node in an AVL tree, self-balancing (zig-zag rotation or the left-right balancing) maintains O(logn) time that is not guaranteed in other unbalanced trees (like BST).
The Balancing ...
0
votes
2answers
248 views
Time Complexity of inserting a vector to a vector of vectors in C++
I was solving a question on LeetCode, where I had to generate all possible subsets of a given set of numbers.
Although, the solution makes sense to me, I am unable to understand the derivation of time ...
1
vote
0answers
53 views
Finding $l$ subsets such that their intersection has less or equal than $k$ elements NP-complete or in P?
I have a set $M$, subsets $L_1,...,L_m$ and natural numbers $k,l\leq m$.
The problem is:
Are there $l$ unique indices $1\leq i_1,...,i_l\leq m$, such that
$\hspace{5cm}\left|\bigcap_{j=1}^{l} L_{i_{j}}...
8
votes
7answers
4k views
Checking equality of integers: O(1) in C but O(log n) in Python 3?
Consider these equivalent functions in C and Python 3. Most devs would immediately claim both are $O(1)$.
def is_equal(a: int, b: int) -> bool:
return a == b
<...
0
votes
0answers
21 views
Time complexity - Head stay transition - Turing Machine
I'm checking time complexity in a turing machine.
There is a transition that doesn't move the head, it justs stays (not right nor left movement) .
Should I count that state transition to calculate the ...
0
votes
1answer
33 views
Complexity analysis of m!/n!(m-n)!
Given the runtime of an algorithm to be m!/(n!*(m-n)!) That is mCn, where both m and n are variables, is the complexity factorial or polynomial? Or is it something else?
Please elaborate.
Thanks
2
votes
1answer
42 views
How do you find all integers in a sorted array of size n that appear n/k times?
I try to find the solution to this problem:
How do you find all integers in a sorted array of size n that appear n/k times in less than O(klogn) time?
I could only find this question, where O(klogn) ...
