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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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
0answers
26 views

Is the spigot algorithm for $\pi$ useful for computing all the digits of $\pi$?

I'm asking the question here because it's not a purely mathematical question and the answer also depends on how computers work. I think that according to the Wikipedia article Bailey–Borwein–Plouffe ...
5
votes
1answer
35 views

Randomized quicksort expected running time analysis

I am following the quicksort analysis in CLRS (pp. 181-184, 3rd edition). Let me summarize the setting of the analysis. Setting in CLRS First let $Z = \{z_1, ..., z_n\}$ be the set of elements of ...
1
vote
1answer
36 views

Average case of simple algorithm like binary search

These questions is about one of my research. As I am not a computer scientist, formal answering is difficult to me. I have a special search algorithm which the explanation here will take a lot of ...
1
vote
2answers
31 views

Time complexity of set intersection

This problem involves the time-complexity of determining set intersections, and the algorithm must give output on all possible inputs (as described below). Problem 1: The input is a positive ...
1
vote
1answer
22 views

Recurrence Substitution Method with multiple givens

Solve by using the substitution method $T(n)=T(n-1)+2T(n-2)+3$ Given $T(0)=3$ and $T(1)=5$ I kind of understand it with only one given and one recurrence call by expanding the call using what is ...
0
votes
0answers
35 views

What is the time complexity of MATLAB's ode solvers?

Say I have a system that is $n$ differential equations that are all coupled together, over a time interval $[a,b]$ with timestep $t$. Is there a straightforward time complexity for MATLAB's built in ...
1
vote
1answer
39 views

Prove $EXP \subset E^E$

I'm trying to prove $EXP \subset E^E$ (strictly). I believe I need to construct my own $A \in E^E$ and show that $A \notin EXP$, but I cannot think of a smart way of doing that. Thanks.
3
votes
2answers
121 views

Skip List estimate number of elements less than (or greater than) a value

I am looking for a thread safe data structure where an element can be searched in $O(\log n)$, for any value, $x$, the number of elements greater than (or less than) can be estimated in $O(\log n)$,...
0
votes
0answers
39 views

Finding reduction to prove that a language is NP-complete

I need to prove that the following problem is NP-complete: We have $n$ diplomats from $n$ countries and we need to seat them around a round table. We also get a list of diplomats who don't get along ...
2
votes
2answers
37 views

Time complexity calculation

I was calculating the time complexity of the following recurrence relation given that T(1) = 1 : T(n) = 2T(n/2) + Logn I was calculating the value and this is where I reached: T(n) = logn + 2log(n/...
1
vote
1answer
49 views

Solve T(n)=T(√n)+ n using substitution method

I am confused how to solve this recurrence equn. after a particular step (step involving ? in the picture) (Plz help me solve the question with same method which I have used and correct if any of the ...
1
vote
1answer
28 views

Complexity of closest set of points in plane problem

Given a set of points on a plane find the set of $n$ points that are closest to the origin. (Points are pairs of integers.) Input: list of points. Initialize a priority queue $Q$, where ...
2
votes
1answer
29 views

How to restore diagonal-symmetric matrix that has been shuffled?

I have a square matrix M, which originally looked like this: 133 199 101 121 142 133 199 101 156 142 133 199 108 156 142 133 (so symmetric around the diagonal). ...
0
votes
0answers
37 views

A list of regex and a list of strings

Given a list A of regex of size n and a list B of strings of size m, you need to output the regex that corresponds to at least one string in B. One way to do is by looping which gives an O(nm). Is ...
0
votes
1answer
23 views

Algorithm to determine which neighborhoods of a graph contain a given set of vertices S

This question concerns determine which sets in a collection of sets contain a given subset S: An undirected graph (V,G) is given with V= {1,..,m}, and given via its neighborhood sets, N(v_1),.., N(...
0
votes
1answer
20 views

What is time complexity in this case?

I have the recurrence of the form T(n) = T(n/2) + O(n) This can be solved using master's theorem and if i use the results of the theorem, the recurrence evaluates to a time complexity of O(n). ...
1
vote
0answers
17 views

Search tree with associative union and worst case insert/delete better than O(n)? [duplicate]

Is there a search tree where union is associative, so $a \cup (b \cup c) = (a \cup b) \cup c$ gives a tree with the same structure? A complete binary tree would be such a tree, but for example a red-...
0
votes
1answer
52 views

Time complexity of transforming one string to another

Here is the problem: Given a dictionary $D$ and two strings $s$ and $t$, write a program to determine if $s$ produces $t$. If it does produce $t$, output the length of of the shortest production ...
2
votes
1answer
43 views

“Fuzzy” Chinese Remainder Theorem NP-hard?

I have some "fuzzy" congruences like these: \begin{align} \\ x&\equiv a_1 \mod 3 \text{ with } a_1 \in \{0,1\},\\ x&\equiv a_2\mod 5 \text{ with } a_2 \in \{0,3\},\\x&\equiv a_3 \mod 7 \...
4
votes
1answer
51 views

Complexity of a graph parity-coloring problem

Suppose I have a positively weighted (bounded-degree) graph $G$ where each vertex in $G$ is colored either black or white. I'm curious about the complexity of the following problem: Find a subset $S$...
2
votes
2answers
117 views

Are there any algorithms that run in (2 ↑ ↑ n)?

I’m wondering whether there are any algorithms that use so much time that they must be represented using Knuth up-arrow notation. Required: Use more than one up-arrow for time complexity. Bonus ...
2
votes
1answer
39 views

Summing two array using FFT: time complexity analysis

This is the problem : Given two arrays of $n$ elements A and B, let's define their sum as $$ A + B = \{ a + b \mid a \in A \text{ and } b \in B \}. $$ Calculate $A + A$ in optimal time given ...
0
votes
1answer
36 views

time complexity of erasing repeated entries

This problem involves the time complexity of erasing entries that occur more than once in a list. I think it might be $n \log n$. Problem The input is a finite set $S$ and a finite list $T$ ...
0
votes
1answer
30 views

Find the computational complexity of a concatenated system

I have a network which includes $L$ blocks ($B_1,\cdots,B_L$) connected one after the other. I have an algorithm having computational complexity $\mathcal{O}(N)$ which runs in each block individually. ...
3
votes
0answers
57 views

“Fuzzy” Chinese Remainder Theorem

I have some "fuzzy" congruences like these: \begin{align} \\ x&\equiv a_1 \mod 3 \text{ with } a_1 \in \{0,1\},\\ x&\equiv a_2\mod 5 \text{ with } a_2 \in \{2,3,4\},\\x&\equiv a_3 \mod 7 \...
1
vote
2answers
50 views

In place and Out place sorting meaning?

What is the meaning of in place and out place in sorting? What are the difference of two of them? Couldn't find any good explanation in the internet.
1
vote
1answer
34 views

Why do we consider the order of growth when analyzing algorithms? [duplicate]

Seriously why do we consider how the computation time time increase with the number of inputs as a measure of performance when we can easily measure such as program execution time,power consumption,...
1
vote
2answers
69 views

The well-known classifiers that can be trained/tested in linear time [closed]

I am interested in collecting the list of the classifiers that (depending on their setting) can have linear time complexity (both in training and testing step) with respect to the number of samples $n$...
0
votes
0answers
27 views

What is the Time Complexity of a Node Learning the Topology of a Graph

O(Diamater) is the time complexity for any node to receive a message from any other node. If there is such an algorithm that every node flooding a message consisting of some information about the ...
0
votes
1answer
12 views

Asymptotic Time Analysis for BFS Tree

Suppose I want to broadcast from my root to all the nodes in a BFS tree. What is the time complexity of this process? I know that it is suppose to be proportional to the depth of the tree, like O(...
3
votes
2answers
82 views

Find the kth smallest element in an unsorted array of non-negative integers

I need to find the kth smallest element in an unsorted array of non-negative integer. kth smallest element is the minimum possible n such that there are at least kth elements <= n. The rub here ...
1
vote
3answers
54 views

How much time would be needed to compute an algorithm with time complexity $O(n^k)$?

How much time would be needed to compute a minimum k-cut, which has time complexity $O(n^k)$ on a graph with $n=5000$ and $k=30$? Consider using a basic 2GHz and 8GB RAM laptop. Please explain also ...
1
vote
1answer
19 views

Exponential Time Classification

If I have a list of length 'n' where each element is a successive power of 2 would an algorithm that simply prints each element decremented to 1 be classified as exponential time? ...
3
votes
1answer
66 views

What is complexity class language $L$ such that $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$?

For language $L$, we have $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$. What is the class of $L$? It is obvious that $L\in$ polynomials. Is there a smaller class for $L$? For example, $...
1
vote
2answers
29 views

$DTIME(f(n)) \subset of DSPACE(f(n))$

I think this is again an easy one: $DTIME(f(n)) \subset DSPACE(f(n))$ They say its trivial but I dont see it, why? And would $DTIME(f(n^2)) \subset DSPACE(f(n^2))$ also be true? if yes why ...
0
votes
2answers
32 views

Time complexity for this simple loop

This is the code: j=2 while j<(n*n) j=j*j At first my approach was to treat this like this loop ...
2
votes
2answers
321 views

P vs NP and can an oracle make P=EXPTIME?

As I understand, diagonalization cannot be used to prove or disprove P vs NP, because for some oracle $A$, $P^A = NP^A$, whereas under another oracle $B$, $P^B \neq NP^B$. I don't fully understand ...
1
vote
2answers
55 views

Show that NP is not equal to SPACE(n)

I want to show that $\text{NP} \neq \text{SPACE}(n)$ and tried it like this: Let $L$ be in $\text{SPACE}(n)$ so there is a deterministic $k$-tape TM which decides $L$ in polynomial time. Let's ...
2
votes
1answer
41 views

No common terms between polynomials: an efficient check?

The "common term" would be in standard form, but the two input multivariate polynomials needn't be, e.g $x(1+y)+y$ and $y(x+a+b)$ have one common term, $xy$. A brute force solution would be to ...
2
votes
1answer
28 views

Why does the insertion-sort algorithm have a quadratic instead of a quasi-linear time complexity?

Can someone explain how the insertion sort have quadratic time complexity and not quasi-linear time complexity in the worst-case? Even in the case of a reversely sorted list, it's not like it'll have ...
1
vote
1answer
33 views

Question on time hierarchy [closed]

How can I prove that $\mathsf{DTIME}^{\mathrm{Htm}}(n^2)$ is contained in $\mathsf{DTIME}^{\mathrm{Htm}}(n^3)$? (sorry about how it is written. I mean the set of languages decided by a deterministic ...
6
votes
1answer
88 views

Is writing a number as two squares and writing the factors of a number equally hard?

Let $L_1$ and $L_2$ be the following: $L_1=\{r:\exists x,y \in \mathbb{Z} \text{ such that } x^2+y^2=r\}$ $L_2=\{(N,M): M<N, \exists 1<d\leq M \text{ such that d|N} \}$ Claim $L_1 \leq_P ...
0
votes
3answers
77 views

Is there an $O(n^2)$ or $O(n^3)$ time algorithm to check if a number is a sum of $k$ elements of sorted array?

Let $A$ be a sorted array of $n$ positive integers (sorted in non-decreasing order, that is there can be equal consecutive elements). Can we check whether some positive integer $x$ is a sum of $k$ ...
0
votes
1answer
46 views

Complexity of Longest Palindromic Subsequence Algorithm

I'm trying to find the longest palindromic subsequence for any string and I've tried two approaches: Recursive Algoritm Dynamic Programming Dynamic programming should be the better option in this ...
2
votes
2answers
85 views

Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the ...
-2
votes
1answer
37 views

Solving double recurrence relation

How to calculate the rate of growth of the below function $f(x)$? $$ \begin{align*} f(x) &= \begin{cases} f(x-1) + g(x) & \text{if } x > 1, \\ 1 & \text{if } x \leq 1. \end{cases} \\ g(...
0
votes
1answer
34 views

Add a road to a network (Graph problem with Dijkstra)

Recently i have found a problem stating: There is a network of roads G=(V,E)(it is not directed) connecting a set of cities V. The length of each road e ∈ E is le. There is a proposal to add one new ...
3
votes
1answer
67 views

Time Complexity: Intuition for Recursive Algorithm

I decide to learn more about dynamic programming, so I started reading the Dynamic Programming chapter from the CLSR book. The first example problem presented there is Rod Cutting (15.1). Given a rod ...
0
votes
1answer
25 views

Can we approximate the number of possible witnesses for an NP language?

Assuming $L \in NP$, meaning that L could be verified by some $V(x,y)$, such that there exists a polynomial $P(X)$ such that $|y| \leq P(|x|)$ for every $x \in L$. I was wondering - can I assume ...
3
votes
3answers
218 views

Is there any difference between Time Complexity and Running time?

Is time complexity and running time of the program/algorithm one and the same thing? Also, running time sounds like 'computer complexity'. As, it utilizes all the resources and give tangible time that ...