Stack Exchange Network

Stack Exchange network consists of 175 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

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 [tag:runtime-analysis] instead. If your question concerns whether or not a computation will *ever* finish, use [tag:computability] instead. Time-complexity is perhaps the most important sub-topic of [tag:complexity-theory].

1
vote
1answer
42 views

Big Oh Time Complexity Involving 'for i in range(n)' [on hold]

Given the code below and the comment analysis: ...
2
votes
1answer
35 views

Time complexity of a problem in probabilistic inference on a Bayesian network

Suppose we have a simple Bayesian network with two rows of nodes: $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$. Each node $x_k$ takes a state of either 0 or 1 with equal probability. Each ...
0
votes
1answer
15 views

Is this computational complexity of the k-NN (custom distance) correct?

I read on a book that in general k-NN (no optimizations), given $d$ dimensions $n$ examples every computation of distance is $O(d)$. Since every example has to be compared with all the other ones, ...
0
votes
3answers
57 views

How can i prove this asymptotic comparison? [duplicate]

This is an exercise that's part of my assignment, but it is optional and flagged as a "challenge". I would like to discuss its solution: Prove that: $$ 27\log{n} + \sqrt{n} = \theta(\sqrt{n})$$ ...
0
votes
0answers
10 views

Determining total of primitive operations and running time for code [duplicate]

i needed some help with these problem in DSA For the given pseudo code: ...
0
votes
0answers
24 views

Computational Complexity of a Matrix Multiplication

I am computing a matrix multiplication with inverse operation $AB^{-1}C$ $A \in \mathbb{R}^{m \times n}, B \in \mathbb{R}^{n \times n}, C \in \mathbb{R}^{n \times o}$. So the inverse operation takes $...
0
votes
0answers
8 views

MissForest package in CRAN R and it’s computational complexity or time complexity? [closed]

Can anyone give me the notation for the time complexity of missforest in R with ‘n’ as the number of instances and ‘m’ as the number of attributes? Is computational complexity as the same as time ...
0
votes
1answer
22 views

Understanding the Linear speedup theorem and how strong it is

Let $k \in \mathbb{N} $ and define the language $L = \{ n,m | n^k = m \}$ Consider a (deterministic) TM deciding $L$ then it has to compute $k$'th power which will take $f(|n|+|m|) + h(k)$ time in ...
1
vote
0answers
30 views

Finding a path with a smallest product

Let $G$ be a graph whose edges have integer weights between 1 and 255. What is an efficient algorithm for finding a path between two vertices $s,t$, such that the product of weights on the path is ...
2
votes
1answer
42 views

How do we prove the time complexity of this simple problem in probabilistic inference on a Bayesian network?

Perhaps a rather trivial question, but I'm trying to refresh on proof methods in CS... Suppose we have a simple Bayesian network with two rows of nodes: $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots,...
0
votes
1answer
70 views

Modified Knapsack Problem

I have a problem with the following optimisation problem: In total there are $n=100$ items. A quality level $L_i \in \{0,1,2,3,4,5\} $ must be selected for each of these items. The greater $L_i$ is, ...
1
vote
1answer
31 views

Interpretation of an asymptotic notation

Assume that we measure the complexity of an algorithm (for some problem) by two parameters $n$ and $m$ (where $m \le n$). What is the formal interpretation of the following claim: there is no ...
1
vote
1answer
27 views

Turing machine algorithms for $\{0^n1^n\}$ using one and two tapes

I was tasked with finding a way to decide the language $A=\{0^k1^k \mid k\ge 0\}$ in $O(n\log n)$ time, and then to implement it on a deterministic Turing machine with one tape. Additionally, I was ...
0
votes
0answers
20 views

Time complexity of this recursive algorithm [duplicate]

Can you help me calculate the time complexity of this recursive algorithm? ...
0
votes
0answers
71 views

Binary search on a path of minimum heap

WhereTo(H,X) is searching for the place to set X (an integer) in a minimum heap-H. The function is executing a binary search on a path of a heap. Assumption: We have the specific path because it ...
1
vote
2answers
74 views

When binary search algorithm will be $O(1)$

I had an exam today, and there was a question that said: Based on the definition of binary search algorithm, discuss when the algorithm time will be $O(1)$ and when it will be $O(\log(n))$. I'm ...
0
votes
1answer
24 views

Coprimes satisfying a pair

We know that number of coprimes less than a number can be found using Euler's totient function. But if there are two numbers $p$ and $q$ and we need to find number of numbers less than $q$ ...
1
vote
2answers
91 views

Decidable problems for which no concrete decision procedure is known

I am looking for an example of decidable problems the decision procedures of which are unknown. I believe someone mentioned one to me once, and I also have read somewhere, but my memory is corrupted. ...
0
votes
2answers
52 views

Can you always prove the asymptotic bound of a recurrence of the form aT(n/b) + f(n) using the substitution method?

To make my question more concrete, here is an example I am stuck on. I want to prove that $T(n) = 8T(\frac{n}{2}) + n^3$ is asymptotic bound by $n^3\log(n)$ using the substution method. That is $T(n)$...
2
votes
1answer
48 views

Time complexity of a tree-based algorithm

I solved a practice interview problem that was sent me by Daily Coding Problem mailing list. I am now curious about the exact time complexity of my solution. Problem Statement Given the mapping a =...
0
votes
0answers
19 views

Analysis Or Review Of Article “Table Design In Dynamic Programming”

I was wondering if anyone could point to some sort of review to this paper "Table Design In Dynamic Programming" by Peter Steffen and Robert Giegerich? https://dl.acm.org/citation.cfm?id=1182768 Has ...
5
votes
3answers
719 views

Fastest algorithm to decide whether a (always halting) TM accepts a general string

Given a TM $M$ that halts on all inputs, and a general string $w$, consider the most trivial algorithm (Call it $A$) to decide whether $M$ accepts $w$: $A$ simply simulates $M$ on $w$ and answer what ...
1
vote
0answers
22 views

Time and space complexity of a recursive problem (code included)

I am having trouble finding out the time and space complexity for this recursive solution. I have to create a list of words in order of word length. Each word, must be one character insertion off from ...
0
votes
0answers
17 views

best first search (lowest cost first search) time complexity [duplicate]

I'm working on a homework assignment directly related to this question: Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis Anyway it's ...
0
votes
0answers
50 views

Termination proof and complexity of a algorithm

I have written the following algorithm $select(\Pi)$ select the first elements from $\Pi$. When there are no element in $\Pi$, it return $\emptyset$. Always terminates .Worst case complexity $O(1)$ $...
0
votes
0answers
15 views

Estimate time complexity of the selection algorithm [duplicate]

Can you, please, help me to get the time complexity of this selection algorithm? Find N-th large element in array I think it is O(n^2) in the worst and O(log n) in the average case. What ways to ...
1
vote
1answer
65 views

Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis

Our professor took three statements from various textbooks that seem to be a little contradictory regarding the complexity analysis of Dijkstra’s algorithm as well as the lowest-cost-first or best ...
1
vote
1answer
43 views

Are all hypothetical machine models for calculating runing time of an alogrithm same?

Im learning about time complexity analysis, and cant seem to figure out why do we consider a hypothetical machine that takes 1 unit of time for arithemitic and logical instructions and 1 unit of time ...
0
votes
1answer
41 views

The time complexity of finding the kth smallest number using buckets

I've implemented kth smallest number using buckets representing the current nibble value of each element in the array where ...
0
votes
0answers
24 views
0
votes
1answer
72 views

Partition array into k subsets

We are given an array and a number K. Partition array into K subsets such that let MaxSum be the maximum sum of among subsets. We have to minimize summation =$$\sum_{i=1}^{k}MaxSum-sum(i) $$ Is ...
7
votes
2answers
819 views

Longest common substring in linear time

We know that the longest common substring of two strings can be found in $\mathcal O(N^2)$ time complexity. Can a solution be found in only linear time?
3
votes
1answer
83 views

Can this equation be solved in polynomial time?

I came across a more general form of this question. Can we find the value of variables in polynomial time ? Let $m = n^{2}$, there are $m$ variables ($x,y,z\ldots$) in the equation and these $m$ ...
1
vote
1answer
83 views

An algorithm that find the max X/Y in a polygon in O(log n)

I got a task to create two functions one finds max $X$ and the other $Y$ in a polygon in $O(\log n)$. The polygon is represented by an array of its vertices where each vertex is represented by its ...
1
vote
0answers
50 views

Can I say θ(g(n)) is the intersection of Ω(g(n)) and O(g(n))?

Let's say Ω(g(n)) be a set representing the lower bound and O(g(n)) be another set representing the upper bound for some function f(n). Can I say that θ(g(n)) is the intersection of these two sets? ...
5
votes
1answer
62 views

How to prove that the time complexity of this algorithm is O($\sqrt{N}$)?

int n; cin >> n; int sum = 0; for (int i = 1; sum <= n; i++) { sum += i; } If I assumed that $N = 100$, the loop will run $13$ steps, ...
1
vote
1answer
27 views

Understanding the relations between O(g(n)), Θ(g(n)) and Ω(g(n)) [duplicate]

I was reading the Cormen, Leiserson, Rivest and Stein textbook, Introduction to Algorithms. The book explained the three asymptotic notations literally very well. However, there was this paragraph: ...
7
votes
2answers
461 views

Find a point shared by maximum segments

Given: $N$ segments (arrays) of ordered integers, integers could be from $-K$ to $K$. Example: ...
2
votes
1answer
168 views

Finding the largest possible area covered by M rectangle under a given histogram

Finding the largest rectangular area possible in a given histogram is a well-known problem and have linear solution. I have a similar but different problem. In my problem, we have $M$ rectangles ...
3
votes
2answers
114 views

How does the bitlength of the divisor affect the running-time complexity of division algorithms?

Wikipedia lists $O(M(n))$ as the best complexity (out of the algorithms listed) for division on two $n$-digit numbers, where $M(n)$ is the complexity of the multiplication algorithm of choice. This is ...
0
votes
0answers
41 views

Relationship between SPACE(t(n)) and DTIME(t(n))

I'm new to complexity theory and am analyzing inclusions between complexity classes. Suppose we are given the following seven complexity classes $DTIME(n)$ $DTIME(n^2)$ $DTIME(2^n)$ $DTIME(2^{2^n})$ $...
5
votes
2answers
541 views

Do I need to consider instance restrictions when showing a language is in P?

I have already shown that 3-colorable for an unrestricted graph is in NP, but I was thinking about the similar language defined as the set of all acyclic $G$, where $G$ such that $G$ is 3-colorable. ...
1
vote
2answers
78 views

What does $O(\alpha(n))$ amortized time mean?

DELETE(S, i): Delete integer $i$ from the set $S$. if $i \notin S$, there is no effect. from a set of consectutive integers like $S = \{1,2,3,5,6\}$ Provide a data structure and an algorithm for ...
2
votes
1answer
80 views

Can all $O(n)$ problems be solved without nested loops?

There are examples of algorithm implementations that contain nested loops but are of complexity O(n), and some of them have corresponding implementations that contain no nested loops. So here comes a ...
0
votes
0answers
72 views

Brute Force Approach for LCS and its Time Complexity

I have read several Algorithm books where it is been told brute force approach of Longest Common Subsequence takes 2^n which is exponential time complexity. Whereas, I've noticed that while I am ...
1
vote
2answers
28 views

Running time complexity of finding maximal power of divisor that divides natural number

Given $n \in \mathbb{N}$, a divisor $p\vert n$, I would like to efficiently find $e\in\mathbb{N}$ with $p^e \vert n$, and $e$ maximal with this property. I will assume that multiplication/division of ...
6
votes
2answers
142 views

Can this system of polynomial equations be solved in polynomial time?

I have these $n$ equations, with $n$ variables. Variables are first $n$ positive integers, constants can be any rational number including zero. Given that there is always a solution, how do we find a ...
1
vote
1answer
52 views

Are there decision problems outside of NP?

Consider any problem in NP-hard, then it has a polynomial reduction from a problem in NP in polynomial time. Though, it isn't clear by this definition whether there are decision problems in NP-hard ...
1
vote
0answers
92 views

CRC computation speed vs polynomials features

I tried to find information about how features of a CRC polynomials influence computation speed of implementations. It is obvious that (depending from the CPU architecture the algorithm runs on) ...