Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 [tag:runtime-analysis] instead. If your question concerns whether or not a computation will *ever* finish, use ...

0
votes
1answer
22 views

All the possible inputs for a given AVL tree

Given an AVL tree,what are the possible inputs so that the same given tree is formed(please dont mention brute force technique)?
1
vote
1answer
45 views

Asymptotic behavior of $n\sqrt n + n \log n$ & $\log_{100} n$ [duplicate]

I have the following two functions $f(n) = n\sqrt n + n \log n$ $\log_{100} n$ And I need to classify them into the followings: $O(n)$, and/or $O(n^2)$, and/or $O(n^3)$, and/or $O(n^{1.5})$, and/or ...
1
vote
0answers
19 views

Algorithms / heuristics for a distributed sorting problem

The setting: There's a cluster of $k$ computers (= node). For simplicity, assume their hardware is identical. The network topology can be complicated, but let's simplify and assume it's a clique ...
1
vote
1answer
20 views

Asymptotic time complexity for finding maximum element in an array

Consider a simple algorithm to find the maximum element of an array containing integers. We just loop through the array, storing the maximum found so far and updating it whenever an element larger ...
1
vote
0answers
13 views

Quantum and classical time complexity

Do we know any function which has same quantum and classical time complexity (bounded error), or at least same upper bound? Of course, let's rule out trivial functions like the constant function, ...
0
votes
1answer
50 views

Is it possible to add every word in a file to a set in $\mathrm{O}(n)$ time?

The Problem: I am currently analyzing a simple program that takes a file of length $n$, splits it into its individual words (seperated by white space) and adds those words to a set: ...
1
vote
1answer
39 views

How to estimate the average time complexity of greatest common divisor?

As we know, the time complexity of $\gcd(x,y)$ is $O(\log \min(x,y))$ by using Euclidean algorithm. Now we fix a constant $n$ and consider the average time complexity of $\gcd(x,n)$. Formally, let $f(...
0
votes
1answer
23 views

Optimizing the problem

I have a recurrence relation: f(a,b) = f(a-1,b)+f(a-2,b-1)+f(a-1,b-1) with conditions: f(0,0)=1, f(a,0)=1, f(0,a)=0, f(x,1)=2*x where the constraints: 1<=a<...
0
votes
1answer
32 views

Evaluating two different Algorithms, which one will scale better?

I'm evaluating two different algorithms to choose one for my implementation, they just do calculations on top of arrays, get some input of $n$ elements, and produce some output of $m$ elements, and I'...
1
vote
1answer
27 views

Algorithm complexity similar to Selection Sort

I'm working on an algorithm that takes an array of $N$ values and it will iterate through each of the values and in each of them iterate through the rest of the array to the right. So the first value ...
0
votes
1answer
59 views

Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm?

Consider algorithms to find shortest paths in a graph. The grassfire algorithm has a complexity of O(|V|) where V is the number ...
-1
votes
0answers
14 views

Computer Graphics Calculation [on hold]

Given a screen of 100px by 200px, calculate the size of a frame buffer needed to store a video clip of 2 seconds when the frame transfer rate is 60 frames per second when the screen is: a) coloured b)...
-1
votes
0answers
12 views

How to calculate time complexity of this program [duplicate]

Hello This is a program for which i want to find the time complexity.
0
votes
0answers
19 views

Given integer of form pq, find p and q if they are prime numbers [duplicate]

We are given number of the form $p\cdot q$ where both $p$ and $q$ are prime numbers, is there efficient and fast way to find p and q? I know that we can find in $O( \sqrt{n} )$, vut can we do it ...
0
votes
1answer
36 views

Will such an algorithm be feasible, will it be considered a poly time algorithm?

Given a p-digit number n, where p is atleast 500, if we have an algorithm whose computational complexity is in the worst case, $O(p\mathrm{log}(p))$, will it be counted as a poly time algorithm ? Or ...
12
votes
2answers
3k views

If lower bound of a problem is exponential then is it NP?

Assuming that we have a problem $p$ and we showed that the lower bound for solving $p$ is $\mathcal{\Omega}(2^n)$. can lower bound $\mathcal{\Omega}(2^n)$ implies the problem in $NP$?
0
votes
2answers
37 views

Help with Time Complexity

Suppose we have the function below: ...
1
vote
2answers
52 views
1
vote
0answers
15 views

Is there a hierarchy theory for time-bounded Kolmogorov complexity?

We know that there are languages in $DTIME(n^t)$ and not in $DTIME(n^s)$ for all $t>s$ due to simple diagonal arguments (i.e., the Time Hierarchy Theorem), but I'm wondering if there is any ...
0
votes
1answer
63 views

Modular exponentiation running time

I read on Wikipedia that modular exponentiation can be done in polynomial time. I've a few questions regarding it (sorry if they seem a bit easy – I'm not a comp sci student). Is it poly ...
-1
votes
1answer
40 views

Measuring infinite loops [closed]

Theoretically, is there a way to measure how many infinite loops are running at a given point in time? In other words, is there a way to freeze everything and get a number on how many infinite lines ...
1
vote
1answer
25 views

Reduce the running by using doubly logarithmic tree

I have two algorithms $A$ and $B$ to solve a problem $P$ of size $n$. Algorithm $A$ takes $O(\log n)$ time on the PRAM using $O(n \log n)$ operations (done in parallel). Algorithm $B$ reduces the size ...
1
vote
1answer
15 views

Represent polynomial time complexity as linearythmic

To determine the experimental time complexity of radix sort, I wrote a program that counted the number of steps the algorithm took to sort N points. I ran that program for multiple N length arrays, ...
1
vote
1answer
63 views

How to describe the time complexity of a continually running program with a stream of inputs?

Maybe time complexity isn't the right term. Performance? There must be some way of describing the efficiency of a program over time. For instance, I recently had a part of a program that took a ...
0
votes
1answer
52 views

Existence of polynomial time reduction from P to R?

Why the next idea doesn't work: If L_2 in R and L_1 in P and the languages are not trivial, then there is a polynomial-time reduction from L_1 to L_2 I know ...
1
vote
2answers
41 views

Is it true that NEXP = EXP when the input binary strings have size O(n)?

I have a question about this. Because if the input binary strings have size of O(n), it takes exponential time to list all possibilities of it. If an language is in NEXP, then we can list all input ...
0
votes
1answer
22 views

Time Complexity of the Kruskal Algorithm after sorting

In case I have sorted edges already, What is the best time complexity of Kruskal Algorithm?
2
votes
2answers
72 views

Time and space complexity of Radix sort

I had previously asked a question on space complexity of radix sort here. I have also read this question. However, I still get confused about it which means that the concept is not clear. I have the ...
0
votes
2answers
81 views

Data structure for finding max, inserting and deleting in O(1) and O(n) space

This is an interview question. I need to implement a data structure that supports the following operations: Insertion of an integer in $O(1)$ Deletion of an integer (for example, if we call delete(7),...
2
votes
2answers
96 views

What is the correct time complexity of the following code

I was wondering what is the correct time complexity expressed in terms of big O on this type of loop: ...
-1
votes
0answers
14 views

Relation between NTIME and SPACE

Why the next isn't true: (Why that fact that NP is contained in PSPACE doesn't help here?) NTIME(n^2017) sub-set-of SPACE(n^5777) And the following is true: (...
0
votes
0answers
16 views

Understanding time complexities of unique data structures

Imagine the following data structure: A pair of arrays where one array is longer than the other, and both arrays are kept sorted. The length of the shorter array is the square root of the length of ...
1
vote
1answer
37 views

Big-O with nested loops and “variables” in the T(n)

So, I need to find the T(n) and then Big-O (tight upper bound) for the following piece of code: ...
2
votes
0answers
24 views

Highest lower bound on an NP complete problem

What is the highest time complexity lower bound that has been proven on any (non-contrived) NP complete problem?
3
votes
3answers
288 views

What are some problems in $\mathrm{P}$ with time complexity of high-degree polynomial?

What are some problems that are in $\mathrm{P}$ but the best known algorithm has a high-degree polynomial ($\ge 3$) time complexity?
0
votes
0answers
41 views

What is the time complexity of this power algorithm?

I'm trying to learn more about time complexity of algorithms on my own, but it comes very confusing when recursion gets into it. The power function calculates $x^...
1
vote
1answer
67 views

Is the problem to construct a $\mathcal{O}\mbox{*}(1.4^n)$ (or better) time algorithm for subset sum still open?

Is the problem to construct a $\mathcal{O}\mbox{*}(1.4^n)$ (or better) time algorithm for subset sum still open? I wanted to check the problem before finishing a paper. The most recent reference I ...
0
votes
0answers
25 views

Algorithm Fragment Analysis

I am not exactly sure what this question is asking: Provide an asymptotic notation for the sum obtained as the result of the following program fragment: ...
1
vote
1answer
29 views

Mathematically calculating time complexity

This is a thread about mathematically calculating time complexity of nonlinear functions. I know that those questions were asked a lot, but it didn't make me understand fully the subject. Also I ...
2
votes
1answer
32 views

Selection Sort Analysis

I'm having difficulty understanding the big-O analysis of the selection sort algorithm. Here is my pseudocode (with line numbers): ...
1
vote
1answer
21 views

Big-Oh and Growth Rate

So, in the book I'm studying from it says : The statement “f(n) is O(g(n))” means that the growth rate of f(n) is no more than the growth rate of g(n). What I understood from this statement is ...
2
votes
1answer
25 views

Travelling Problem with Constraints

Consider a network with $N$ nodes $1,...,n$. Every node is connected to every node via a weighted edge, where the weight represents distance. You start your travel at a given node, say $1$, and end ...
0
votes
0answers
14 views

Single Pass in Memory Indexing

I was reading single pass in memory indexing and had few doubts. Why is the time complexity of SPIMI O(T) where T are the token. We know that before writing blocks to Disk, we have to sort ...
1
vote
1answer
19 views

Should I keep a relevant constant in the Time Complexity?

I designed an algorithm, and the Time Analysis provided next time complexity: $\mathcal{O}(2^p \cdot (\frac{t}{2}/2^p) \cdot \frac{n}{4})$ what must be simplified to: $\mathcal{O}(2^p \cdot \frac{...
1
vote
2answers
105 views

Best time complexity of sorting numbers in range [1…n log n]

given an array $A$ of $n$ numbers in range $1$ to $n\log n$, what is the time complexity of the best method to sort them? The answer is $O(n)$ but I don't understand this. of course counting sort ...
2
votes
2answers
62 views

Proving time complexity of $T(n) = 2T(n/3 + 1) + n$

I am working on proving the time complexity for the following problem, but believe I am stuck: $$T(n) = 2T(n/3 + 1) + n$$ I have checked out this link here on time complexity on cs.stackexchange ...
1
vote
1answer
41 views

Solving Recurrences Using Master Method [duplicate]

Using the Master Method, I need to prove (True, or False and why) the following (3) recurrences: $T(n) = 3T(\frac{n}{2}) + n = \Theta(n\ln(n))$ $T(n) = T(\sqrt{n}) + 1 = \Theta(n^2)$ $T(n) = 2T(\frac{...
1
vote
0answers
27 views

Calculating the complexity of an algorithm exercises [duplicate]

I am really bad at calculating correctly the complexity of a given algorithm. I would like to know if there is some book or online resources where I can find many exercises that ask to calculate the ...
1
vote
3answers
74 views

Time complexity of function vs return value

I came across following problem: Find the time complexity of below recurrence relation: $T(n)=\begin{cases} & 2T(n/2)+C; & n>1\\ & C;&n=1 \\ \end{cases}$ The solution ...
1
vote
1answer
29 views

Understanding $DSPACE(s(n)) \subseteq DTIME(2^{O(s(n))})$

I'm having trouble understanding this statement: $DSPACE(s(n)) \subseteq DTIME(2^{O(s(n))})$. The logic is that $2^{O(s(n))}$ is the total number of different configurations a Turing Machine M that ...