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
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
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
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 ...

1 2 3
4
5
38