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.
2,479
questions
1
vote
1
answer
83
views
Would this be the correct time complexity?
I'm currently working on an exercise that has made me ponder for a bit. The following exercise is from the 6th Edition of Data Structures and Algorithms in Java:
An inverted file is a critical data ...
- 225
2
votes
1
answer
738
views
What is the amortized cost of pulling top K elements from a priority queue?
To pop an element off of a priority queue, the worst-case complexity is:
O(logN) where N is the number of elements.
Now if you do K pop operations on the priority ...
- 115
0
votes
1
answer
171
views
Time-complexity of evaluating a CNF formula
Given a Boolean formula over $n$ variables in CNF and a partial assignment to it, all the algorithms I can think of to evaluate the assignment run in time $\Theta(n^2)$. Is it possible to do it in $O(...
- 219
1
vote
4
answers
526
views
Stable sort an array with k distinct elements, each appearing double the times the previous one appears
I've started with thinking of a bucket sort/radix sort variation, only to be disproved by a colleague.
Here's the problem:
Given an array with $k$ distinct elements, it is known that the
smallest ...
- 306
1
vote
1
answer
178
views
Limited tapes-version TM for pair sum
In the problem of pair-sum we are given a multiset $A$ and a number $\alpha$. We are asked to find whether there is a pair ($2$ numbers) of $A$ s.t. their sum is $\alpha$. Here all numbers are small/...
- 113
0
votes
0
answers
11
views
Are there any examples of quantum simulator programs than run faster or use less memory than similarly idiomatic classical analogs?
I'm curious if there are any examples of programs written for quantum simulators that are more performant (time or memory) than their classical analogs.
I acknowledge that at simulator runtime these ...
- 133
0
votes
0
answers
17
views
Learner Algorithm Time & Sample Complexity
Let $X=R^{2}$. Let $u=\left(\frac{\sqrt{3}}{2},-\frac{1}{2}\right),\
w=\left(-\frac{\sqrt{3}}{2},-\frac{1}{2}\right),\ v=\left(0,1\right)$
and $C=H=\left\{h\left(r\right)=\left\{\left(x_{1},x_{2\ }\...
- 221
0
votes
0
answers
64
views
Complexity of finding the kth smallest element of all the elements in two order statistics binary search trees
What is the time complexity of finding the kth smallest element of all the elements in two order statistics binary search trees? An order statistics tree is a binary search tree where the size of a ...
0
votes
0
answers
57
views
How will changing the splitting point in merge sort affect the algorithm and its time complexity
Everyone knows that merge sort will continuously divide the array into halves until they are small enough to (like 2 elements per block or so) be able to be sorted quickly, hence its time complexity ...
- 1
1
vote
0
answers
39
views
Are there computational complexity results for generative adversarial networks?
First time posting on here; if this question is too rough I would appreciate if you could point me to a stackexchange forum where this question may be a better fit.
Generative adversarial networks (...
- 11
0
votes
0
answers
79
views
Modification on Boyer Moore Algorithm to find an element that occurs more than n/3 times
Given an array of numbers with length $n=3^k$, we try to find an
element that occurs more than $\frac{n}{3}$ times. So work as follow:
We divide the array into 3 parts of equal length. Find
...
- 1
1
vote
1
answer
554
views
Time Complexity of ${n \choose k}$
I want to know the time complexity of specifically calculating ${n \choose k}$ where it is defined as
$$
{n \choose k} = \frac{n!}{k!(n-k)!}.
$$
If the factorial function is recursive $O(n)$:
...
- 161
0
votes
1
answer
91
views
Does a constant time compression algorithm proves that P=NP?
Supposed someone came up with a compression algorithm that doesn't iterate through bytes or anything to compress data, does that proves P=NP?
That is, an algorithm that doesn't rely on patterns/...
0
votes
2
answers
59
views
A little confusion with Big Theta time complexity
I came across one Big Theta expression:
Here I am thinking this expression to be valid. But please correct me as the answer doesn't goes in the same way.
As per definition of Big Theta.. any function ...
2
votes
3
answers
253
views
Find the smallest difference between two numbers in a DS in O(1) time
I got an assignment to create a new data structure, with the following rules:
Init - O(1).
Insert x - O(log$_2$n).
Delete x - O(log$_2$n).
Search for x- O(log$_2$n).
Find max difference between two ...
- 23
0
votes
0
answers
72
views
Find a set K of k vertices in a graph such that the distance between any vertex to the closest vertex in K is minimized
Given a graph with $V$ vertices and $k$, find a set $K$ of $k$ vertices of $G$. Let $c(v)$ be the distance (in BFS-like) of the vertex $v \in V$ to the closest vertex $u \in K$. How to choose the set $...
- 101
0
votes
0
answers
40
views
Time complexity of find() operation for a Merge-Find Set
Given a Merge-Find Set implemented using a set of linked-lists, my professor says that the time complexity of find() operation is O(1). Each element of the lists ...
- 347
2
votes
1
answer
85
views
Is $m \log^2 n$ complexity too much?
I have been struggling for a few hours in terms of finding the right solution for the following problem:
Suppose we have a file that contains integers where each represents a user of a service. By ...
- 225
2
votes
2
answers
129
views
Exponential Time Hypothesis and the input size vs number of variables
According to Exponential Time Hypothesis there does not exist a deterministic algorithm to solve SAT over $V$ variables in time $o(2^V)$. However, let's say the number of literals $n = \omega(poly(V))$...
- 1,393
2
votes
2
answers
50
views
Delete consecutive characters and add zeros at the end with a restriction
Given an array of characters, I need to delete all the characters that got repeated 3 or more times (consecutively) and add '0' at the end of the array for every deleted character,
The restrictions:
$...
- 21
1
vote
1
answer
247
views
Time Complexity of Exponentiation Operation as per RAM Model of Computation
Now, $\color{blue}{\text{Exponentiation}}$ is defined as
Exponentiation is a mathematical operation, written as $b^n$, involving two numbers, the base $b$ and the exponent or power $n$, and ...
- 251
1
vote
1
answer
114
views
Time complexity analysis for dynamic programming using memoization
I am trying to figure out the time complexity for "Regular Expression Matching" problem.
Problem statement is simple, only meta characters allowed are '.' and '*'. Actual problem statement ...
1
vote
1
answer
62
views
Complexity of finding $d$ largest eigenvectors of a symmetric matrix
I know that for $n \times n$ matrix, it takes $O(n^2)$ time complexity to compute the largest eigenpair of the matrix using Power method or etc. I'm interested to further extend the case so that now ...
- 123
0
votes
0
answers
87
views
Worst case lower bound of the general number guessing problem
I have the following problem:
Let Alice and Bob be two people playing games.
Alice and only Alice owns a special device, Robo, that is capable of generating one truly random number $k \in \mathbb{N}$ ...
0
votes
2
answers
221
views
Finding Median value given a tuple (value, frequency) in O(n) worst case time complexity
An accountant in a big firm would like to find the median of the
salaries of all employees. The data they received is a list of size n
containing the tuples $\left\{s_{i\ },f_{i\ }\right\}_{i=1}^{n}$,
...
- 221
0
votes
1
answer
52
views
equivalency of some facts in $O$ notation
I misunderstanding about some logarithm property in algorithm course:
is it correct that we say following three term is equivalent?
$O(\log a + \log b)$
$O(\log (ab))$
$O(\log (a+b))$
- 381
1
vote
1
answer
58
views
Subdivide a graph into non-crossing triangles with maximum edge weight
Let $G=(V,E)$ be a complete finite graph with the vertices arranged in a circle. Each edge has a nonnegative weight, and we would like to find an efficient algorithm to find a subgraph of maximum ...
- 303
2
votes
2
answers
76
views
What is the lower bound on retrieving an item in a collection if no arrays(Random access memory) are allowed?
I know that retrieving an item in a collection can be done in $O(1)$ time(on average) using hash tables. I would like to know if there is an algorithm that could be as performance without using arrays....
- 235
2
votes
1
answer
47
views
Complexity of a restricted SAT problem
I am wondering about the complexity of the following SAT related problem:
Given a CNF with $n$ clauses containing exactly $k$ literals with the following properties:
The intersection of any pair of ...
- 23
1
vote
1
answer
172
views
Find a path with given weight and the minimum number of edges on a tree
Suppose given a positively-weighted tree $T=(V,E,w)$ and $k\in \mathbb{N}$, where $|V|=n$, the weight function $w:E\to\mathbb{N}$, and each node has degree at most $3$. How we can find a path on $T$ ...
- 1
4
votes
1
answer
701
views
Count the number of intersections of n chords of a circle in O(n log n) time
Suppose you are given two sets $\{p_1, p_2,\dots , p_n\}$ and $\{q_1, q_2,\dots , q_n\}$
of $n$ points on the unit circle. Each point $p_i$ is connected to $q_i$ by a line segment. How could we count ...
- 1
0
votes
0
answers
80
views
The total number of nodes and the height of a ternary search tree
So I need to insert into the ternary search tree (TST) about N strings. Each string is a unique ID "consists of 10 letters, the first 3 are upper case letters and the last 7 are digits" for ...
3
votes
2
answers
461
views
Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n
Given the recurrence
$$T(n) = 2T\bigg(\frac{n}{8}\bigg) + 2T\bigg(\frac{n}{4}\bigg) + n$$
My professor says that $T(n)$ is $O(n\log n)$ but I have calculated a complexity of $O(n)$ as shown below with ...
- 347
0
votes
1
answer
132
views
Is it faster to use Counting Sort to lexicographically sort characters in a word in Python?
Assuming I have very long words, is it worth it to use Counting Sort with its memory overhead to achieve linear time complexity?
I wrote a Python function that sorts the characters in a given string ...
- 1
2
votes
1
answer
140
views
Cost of increasing a binary counter with a starting value n times
Consider a k-bit binary counter and suppose that in the beginning the value of the i-th most significant bit is $b_i$ for each $i = 0, . . . , k − 1$. Let $b = b_0 + 2b_1 +· · · + 2^{k−1}
b_{k−1}$. ...
- 391
1
vote
1
answer
227
views
Why do hash tables have no access/indexing complexity but have $O(1)$ search complexity?
Sources:
https://en.wikipedia.org/wiki/Best,_worst_and_average_case
https://www.bigocheatsheet.com/
It can be seen that a Hash Table has no access/indexing complexity given the above sources. This ...
- 381
2
votes
1
answer
81
views
Efficient data structure to maintain a set of postal codes and mailbox numbers
A 'person' is represented by a combination of postal code and mailbox number(both are natural numbers)
No two postal codes are alike, yet a postal code can contain many different mailboxes.
At any ...
- 306
1
vote
1
answer
37
views
Comparing two functions rate of growth
This is pretty simple and I THINK I know the answer to the question, but I don't know how to prove it formally. Below follows the question.
Question. Compare the functions $f(n) = \frac{n^2}{\log(n)}$ ...
- 187
1
vote
1
answer
67
views
an O(m+n) algorithm to decide whether a graph can be reduced to a single edge with two vertices
Given B and C operations.
B-operation: When two multi-edges connect a pair of vertices, replace the multi-edges with a single edge connecting the pair of vertices.
C-operation: When one edge ...
- 173
0
votes
1
answer
78
views
Sorting optimization to presorted array
I'm looking up the complexities of sorting algorithms. There can be performance harm when the array is already presorted when running certain algorithms. E.g. Using last element as pivot in quick sort ...
- 101
1
vote
1
answer
111
views
A decidable language that can't be decided by a circuit ensemble of linear size
Let Size(O(n)) be the set of languages the can be decided by a circuit ensemble (a sequence of circuits C_i for every natural i s.t input size is i) such that every circuit's size is linear (in input ...
- 11
0
votes
0
answers
32
views
4
votes
1
answer
277
views
What are efficient approaches to implement unit propagation in DPLL-based SAT solvers?
I'm trying to decompose deduction steps of DPLL algorithm -- unit propagation and pure literal elimination -- for parallelization. However, I want a baseline and asymptotic analysis to compare to my ...
- 43
2
votes
2
answers
641
views
Doubt about computing running time / time complexity of a function in Python
I am learning about time complexity now, and I am working with BST (Binary Search Trees).
This question needs some context and this is a follow up post to this post. Basically, I would like to compute ...
- 187
1
vote
2
answers
481
views
Averege time complexity of open addressing
I get that it depends from the number of probes, so by how many times the hash code has to be recalculeted, and that in the best case there will only be one computation of the hash code and the ...
- 115
0
votes
0
answers
161
views
Time Complexity of dependent nested loops
I'm recently in to the algorithms and I'm having trouble finding the time complexity(Big-Oh notation) of the following algorithm:
...
- 1
0
votes
1
answer
98
views
Understanding time complexity of algorithm to determine if parenthesis are matching
Both these algorithms determine if all the parenthesis in a string are
balanced and properly nested.
The first algorithm uses "a constant amount of memory, regardless of the length of
the string.&...
- 13
3
votes
1
answer
102
views
Find the flaw in the 3SAT solver algorithm
I consider decision version of 3SAT problem.
Main idea is to find congruent clauses and construct such maximum formula,
which satisfiability/truth table won't be changed.
In case of unsatisfiable ...
- 199
2
votes
2
answers
79
views
I need help finding the complexity of an algorithm
i have the following algorithm :
j = 1
while j ≤ n do
j = 2^j
where n is our input and is a non negative integer
I found the complexity of the algorithm to be O(1) . Can someone tell me if this is ...
- 29
1
vote
0
answers
21
views
Algorithm Complexity Question
this is my first question on this site and I would like to preface this by saying I am not very savvy when it comes to Computer Science. So, I will try to ask this the best I can.
I was doing some ...
- 51