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
0
votes
0answers
23 views
How to explain that a program that runs in NTIME(O(lg n)) is in the class P?
if a non-deterministic program executes only lg(n) decisions on each branch of the computation tree, then the problem this program solves is in P? That means, there is a deterministic algorithm that ...
3
votes
1answer
50 views
Big-O when iterations do not correlate with input
Sorry for the perhaps basic question, but my time at university is long ago and I need to brush up on Big-O stuff for interviews.
My question is, what would the time complexity be when an algorithm ...
0
votes
2answers
33 views
Searching for an algorithm with $\Theta(n2^n)$ time complexity
I am searching for an algorithm with a time complexity of $\Theta(n2^n)$ time complexity.
I am aware, that e.g. the Fibonacci sequence has a time complexity of $\Theta(2^n)$.
My plan was to add a loop ...
3
votes
1answer
49 views
When do you use amortized time complexity and when to use unamortized?
This is my guess:
-Use amortized because we want to know the "averaged" complexity over n operations assuming the ...
0
votes
0answers
20 views
String membership in hash set time complexity
Given a string s and a hashset of strings words, what is the time complexity of the operation: ...
0
votes
1answer
49 views
What are the $EXP^{NP}$, $EXP^{PSPACE}$, and $EXP^{EXP}$ equal to
What are the $EXP^{NP}$, $EXP^{PSPACE}$, and $EXP^{EXP}$ equal to?
I suspect that their, NEXP, ESPACE and 2EXPtime respecitvely.
And what bout $NP^{EXP}$
2
votes
1answer
3k views
Building heaps and heapsort using linked list
I know that linked list is not a appropriate data structure for building heaps but I am interested in knowing the time complexity of building heaps and heapsort using linked list.
One of the answers ...
0
votes
1answer
52 views
How is the NP verifier polynomial?
If we start with the definition of L being in NP if "there exists a polynomial NTM that decides L" (where polynomial for an NTM means the length of the worst run as a function of the size/length of ...
5
votes
7answers
2k views
The running time of algorithm is at most $O(n^2)$
The problem is that if an algorithm is $O(n^2)$ then it is also $O(n^3)$ and $O(n^4), O(n^n), \ldots$ and the phrase 'at most' does not make sense in this situation.
For this reason, I am not sure ...
3
votes
2answers
81 views
Meaning of 'running time is $O(n^2)$'
I have a question from Introduction to Algorithms by CLRS,
When we say "the running time is $O(n^2),$" we mean that there is a function $f(n)$ that is $O(n^2)$ such that for any values of $...
1
vote
1answer
52 views
In Strassen's algorithm, why does padding the matrices with zeros not affect the asymptopic complexity?
In Strassen's algorithm, why does padding the matrices with zeros, in order to multiply matrices that are not powers of 2, not affect the asymptopic complexity?
Hi, I was reading this question but I ...
1
vote
1answer
41 views
Determing Big Oh Of Given Data
I'm trying to determine the big O time complexity of the following
data set where the first column is the input size, and the second column is the execution time in seconds. Where possible, I should ...
0
votes
1answer
55 views
Time complexity of removing a vertex from a graph represented as collection of adjacency lists
I'm trying to reason about the time complexity of removing a vertex from a graph represented as an adjacency list, which has $n$ vertices and $e$ edges. It is a directed graph, and the list associated ...
0
votes
1answer
38 views
Exact runtime of median of median algorithm
Consider median of median algorithm. If I make to group of size $7$ instead of $5$ then the recurrence equation will be
$$T(n)=T(n/7)+T(5/7\cdot n+4)+O(n),$$
which can be proven by induction equal to $...
0
votes
1answer
29 views
Algorithm for assigning items to one of two sets (2-CNF?)
I have a set of items (A, B, C, D, ...) which I want to assign to one of two sets (set1, set2). Trying all possible assignments ...
-2
votes
1answer
34 views
Solution to T(n) = 2T(n/2) + log n
So my recursive equation is T(n) = 2T(n/2) + log n
I used the master theorem and I find that a = 2, b =2 and d = 1.
which is case 2. So the solution should be O(n^1 log n) which is O(n log n)
I looked ...
0
votes
0answers
28 views
Time complexity of a recursive algorithm with two lists as parameters
The goal is to find the function T which describes the time complexity of an algorithm who merges two lists (but the lists are given inversely sorted). The problem is that recursive calls depend on an ...
1
vote
1answer
54 views
Counting occurrences of word in a text
Let's say I have a long text of 1M words and I would like to create a table of all the words ordered by the number of occurrences in the text.
One approach would be populating a dynamic array with ...
0
votes
0answers
27 views
Computational complexity of described algorithm
Is algorithm which schedules tasks to machine and then for every time point in the makespan of machine does an operation considered pseudo-polynomial or quasi-polynomial? (if machine execute tasks ...
0
votes
1answer
62 views
Classification and complexity of generating all possible combinations: P, NP, NP-Complete or NP-Hard
The algorithm needs to generate all possible combinations from a given list (empty set excluded).
...
0
votes
0answers
25 views
Is there a decision problem in NP whose corresponding function problem is not in #P?
I am trying to get an imagination of the class #P for my bachelor thesis. Right now I think of it as a DTM that runs every possible path to run an algorithm on some decision problem at once. But in ...
1
vote
0answers
40 views
Complexity in time and memory for graph search algorithm
I am working on an assignment where I have to write an algorithm to detect all vertices that lie in a cycle in a graph and then calculate its complexity. I have come up with an algorithm in pseudocode....
1
vote
2answers
893 views
reducing $CLIQUE$ from decision to search problem
consider the language:$$CLIQUE = \left\{\langle G,k\rangle \ |\ \text{ $G$ is a graph containing a clique of size at least $k$ } \right\}$$
Suppose there's a polynomial time algorithm for $CLIQUE$. ...
4
votes
3answers
295 views
Two increasing functions from the set of positive integers to the set of positive integers such that neither f (n) is O(g(n)) nor g(n) is O(f (n))
Here is the question again : Give an example of two increasing functions f (n) and g(n) from the set of positive integers to the set of positive integers such that neither f (n) is O(g(n)) nor g(n) is ...
0
votes
0answers
28 views
what is the complexity of the below code? [duplicate]
I wanted to calculate the complexity of this pseudocode. In my knowledge, it is $n^2$ because the last loop only runs 8 times. I wrote a program to test it tends to run 8^logn (approximately). can you ...
2
votes
1answer
383 views
Finding the rectangle with maximum perimeter weight in a 2D array
[Problem Description]:
Given an array of size $N \times N$, the task is to find the rectangle with maximum perimeter weight in the array. The perimeter is defined as the number of cells on the sides. ...
1
vote
1answer
37 views
A problem about master theorem and recursion [duplicate]
Prove or disprove the following statement:
If $f(n)\in \Omega(n^2)$ and $T(n) = 2T(n/2) + f(n)$ then $T(n) \in O(f(n))$.
I think that the statement is false.
Do you know any counterexamples?
0
votes
0answers
35 views
The following time complexity is right for the given algorirthm
Calculate the complexity of the algorithm as follows O (n ^ 2) Would it be correct?
...
4
votes
3answers
76 views
What is the difference between saying there is no Ļµ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time and $n^{2-o(1)}$ or $\Omega(n^2)$?
I have seen the formulations
there is no Ļµ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time
a problem requires time $n^{2-o(1)}$
a problem requires time $\Omega(n^2)$
being used ...
0
votes
2answers
47 views
Time complexity of ArrayList Insertion : Calculating sum of X + X/2 + X/4 + X/8 + … 1
Here is an excerpt from Cracking Coding Interview book where it's talking about the time complexity of insertion to an ArrayList.
I am trying to prove that the sum of $X + \frac{X}{2} + \frac{X}{4} + ...
4
votes
3answers
971 views
What is the expected time complexity of checking equality of two arbitrary strings?
The simple (naive?) answer would be O(n) where n is the length of the shorter string. Because in the worst case you must compare every pair of characters.
So far so good. I think we can all agree that ...
0
votes
0answers
60 views
Why the time complexity for following pseudocode is O(n^2)?
So, I was going through the Rod-Cutting problem in the Dynamic Programming section of the Introduction to Algorithms by CLRS.
Here's the rod-cutting problem statement: Given a rod of length n inches ...
0
votes
0answers
23 views
Counting elements in an array greater than a value and after the value
I have an array composed of integers from 1 through n. For each integer, I want to count the integers which are greater than that integer and occur after the integer's placement in the array in O(n*...
1
vote
1answer
80 views
Complexity of Radix Sort
I am a little confused by the complexity proof of Radix Sort.
For counting sort, the complexity reported is $O(n+R)$, where $n$ is the number of items and $R$ is the range.
But this is not entirely ...
0
votes
1answer
51 views
Comparing the big-$O$ of these four functions
Sometimes you can substitute values for $n_0$ and $c$ in the big-$O$ equation and compare two functions. Or take limits and compare two functions.
But for the following functions, for example, taking ...
0
votes
0answers
55 views
Create a potential function for an abstract queue data structure to show constant amortized-time complexity
Consider a variation of a Queue called MaxQueue, Q, that has the following operations:
dequeue(Q): removes and returns the first element of Q
enqueue(Q, s): Appends the integer s to the end of Q
...
2
votes
2answers
43 views
Algorithmic problem with many different time/space complexity solutions
I am preparing a lesson about algorithmic thinking for beginner programmers. I would like to show them an easy to understand problem which has as many solutions as possible with different time or ...
0
votes
0answers
73 views
Time complexity for computing the highest degree vertex
Consider an undirected and unweighted graph with $n=|V|$ nodes and $m=|E|$ edges stored in adjacency matrix format.
What is the time complexity of finding the highest-degree vertex, assuming the ...
1
vote
1answer
27 views
Range sum query - tree representation efficiency
I was reading about possible solutions to the well known problem:
Given array A with length N create a structure that enables
...
0
votes
0answers
4 views
Complexity Analysis for complex nested loops [duplicate]
What is the general approach for time complexity analysis when you have a loop structure which is complex?
For example if the length of the inner loop is some function o the iteration of the outer ...
2
votes
2answers
52 views
Why do algorithms with runtime of O(n) are said to have asymptotic upper bound, when linear functions don't have asymptotes?
When we have only an asymptotic upper bound, we use $O$-notation. For a given function $g(n)$, we denote by $O(g(n))$ (pronounced ābig-oh of $g$ of $n$ā or sometimes just āoh of $g$ of $n$ā) the set ...
1
vote
1answer
420 views
heap data structure complexity
I'm trying to count running time of build heap in heap sort algorithm
...
0
votes
1answer
225 views
what would be the time complexity of DBSCAN algorithm?
what would be the time complexity of DBSCAN algorithm if we use it for graph(sparse) clustering $O(n^2)$ or $O(n \log{n})$?
2
votes
1answer
44 views
Is it true that $f(n) = c\cdot g(n) + O(g(n))$ implies $f(n) = O(g(n))$?
Is this true for all $n$ and some $c>0$? I'm thinking the answer is yes, but I'm not sure. My thinking is as follows:
$f(n) = c\cdot g(n)$ for all $n$ and some $c>0$ is the definition of Big-Oh.
...
0
votes
2answers
50 views
Choosing Constant for Last Step in Substitution METHOD $T(n)= 5T(n/4) + n^2$
I figured out a solution to a recurrence relation, but I'm not sure what the constant should be for the last step to hold.
$T(n)= 5T(n/4) + n^2$
Guess: $T(n) = O(n^2)$
Prove: $T(n) \leq cn^2 $
...
1
vote
0answers
28 views
A genral Turing model with one tape to define sublinear space (L,NL,..)
A genral Turing model with one tape to define sublinear space (L,NL,..)
Normally to define sub-linear space complexity we need special Turing models with many tapes, at least two: a read-only tape and ...
5
votes
1answer
75 views
Maximize area of light with 4 light sources on a diagram of a room
Given a diagram of a room with obstacles in it (like walls or furniture), find the 4 best places to put omnidirectional light sources in it so the area that is lighted is maximized.
Here is a simple ...
2
votes
3answers
61 views
Determining the number of iterations needed to find the number of bits in an integer
I'm trying to understand the complexity/number of iterations needed to determine the number of bits in an integer.
...
1
vote
1answer
65 views
What is $f(n)$ in $NTIME(n)\subseteq DTIME(f(n))$ if $CIRCUITSAT$ is in $P$?
If $CIRCUITSAT$ in $n$ variables and $m$ gates has an $O((nm)^c)$ algorithm for a fixed $c>0$ then $NTIME(n)\subseteq DTIME(O(f(n)))$ for large enough $f(n)$. What is the smallest $f(n)$ in $NTIME(...
1
vote
1answer
25 views
Lowest complexity - Number closest to 0
I'm currently trying to improve my algorithm skills and I was trying a simple algorithm :
Given a list of integers. We want to find the one that is the closest to 0. If we have a number and his ...
