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
2answers
164 views

Time complexity of pairs in array double loop

I know, that the following is: O(n^2), ...
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) ...

1
3 4
5
6 7
38