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

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

1
vote
1answer
26 views

Compute the general time complexity of a merge sort algorithm with specified complexity of the merge process

The problem was from an exam, I spent much time wrapping my head up around this kind of problems, so I decided to ask for help ;( Problem: We implement a merge sort algorithm to sort $n$ items. The ...
1
vote
1answer
25 views

What is the meaning of max() in intro. to algorithms?

I'm reading chapter 3(growth functions) of CLRS and in giving an example of proving theta for a standard quadratic function the book gives the following value for $n_0 = 2 \cdot max(|b|/a, \sqrt{|c|/a}...
0
votes
0answers
31 views

Minimum finger search tree complexity

Suppose I have an AVL tree with a pointer to the minimal element. I'd like to conduct a search for some key x, which is the k-smallest key in the entire tree. I can do this by "climbing" up the tree's ...
0
votes
0answers
26 views

Dynamic Programming : Recovering Optimal Solution: Refer Tardos

"So far we have simply computed the value of an optimal solution; presumably we want a full optimal set of intervals as well. It would be easy to extend M-Compute-Opt so as to keep track of an optimal ...
-1
votes
0answers
18 views

Understanding the time complexity of merge sort [duplicate]

What is an explanation of why merge sort runs in $\Theta (n \log_2 n)$ time?
-3
votes
0answers
36 views

Can you tell me what is the big o of this question with solving it? [duplicate]

Sum<-- 1 For i<-- 1 to n do for j<-- 1 to i^2 do if j mod i=0 Then for k<-- 1 to j do sum<-- sum + 1 Maybe O(n^4)
3
votes
1answer
75 views

Can a list with $\mathcal{O}(1)$ access have an insertion complexity better than $\mathcal{O}(n)$?

It seems intuitive that there's no list data structure which has $\mathcal{O}(1)$ worst case time complexity for random access and a worst case complexity better than $\mathcal{O}(n)$ for insertion: ...
0
votes
1answer
33 views

How can I create zero-collision-free strings more efficiently?

$S$ is a symmetric set If $|S|=3$ such that $S=\{n_1, n_2, n_3\}$ then $n_1+n_2 = n_3$, If $|S|=4$ such that $S=\{n_1, n_2, n_3, n_4\}$ then $n_1+n_3=n_4$ and $2n_2=n_4$, If $|S|=5$ such that $S=\{...
1
vote
1answer
33 views

Getting N top scores from a matrix

I start with a matrix, lets say 4x4. So I want the N top scores, with the sum of one element of each row. For example: ...
0
votes
1answer
28 views

Showing that algorithm has STOP property and finding its computational complexity function

The task is to show that given algorithm has STOP property and to find its computational complexity function. $\alpha:$ $n \ge 0$ ...
3
votes
1answer
66 views

Find all values repeating more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time

Given a parameter $k$ and an array (not sorted) of length $n$ return all values which repeat more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time. I've managed this in $O(nk)$ time, but can't ...
4
votes
2answers
46 views

Find two numbers in array $A$ such that $ |x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time

I'm struggling with the following question: Let $\langle a_0, a_1,\dots,a_n\rangle$ be a sequence of real numbers, and let $ M = \max\{a_0, a_1, .... a_n\} $ and $ m = \min\{a_0, a_1, .... a_n\} $....
4
votes
3answers
103 views

Can we remove duplicates faster than we can sort?

The problem is (integer) duplicate removal, which can also be perceived as producing the image of an evaluated function (of integers): Given a sequence $S_\text{in}$ of $n$ integers, produce a ...
0
votes
1answer
15 views

Forming polylines from a list of individual lines

I want to optimize a SVG path made entirely of lines. Given a list of lines, each made of two 2D points connected together, I want to find an equivalent list of polylines. For example: ...
1
vote
3answers
66 views

Is this algorithm of constant time?

I have the following code in Python: ...
0
votes
0answers
13 views

Circuit class with smaller than O($\log n$) depth

In general NC$^1$ is the class of bounded fan-in circuits with depth $O(\log n)$ and AC$^0$ is the class with unbounded fan-in circuit with depth $O(1)$. Where does the class of circuits with bounded ...
0
votes
2answers
44 views

How can I solve the recurrence $f(n) = 3f(\frac{n}{4}) + \log(n)$?

The master theorem didn't work here. I tried to do the substitution method but I ended up with an additional term: $2Σ(i \cdot 3^i)$. Also I should find the solution $g(n)$ such as $f=\Theta(g)$.
0
votes
0answers
27 views

How do I find the time complexity for the “Collect maximum coins” DP solution? [closed]

can any one help me to analysis this algorithm in details Check the following link: https://www.geeksforgeeks.org/collect-maximum-coins-before-hitting-a-dead-end/ there is two solutions for this ...
-1
votes
0answers
11 views

cyclomatic complexity of resursive function

My aim is to find the cyclomatic complexity of the code,but this involves a recursion so i am confused whether the recursive statement will take it to the beginning in cfg. Can anyone confirm..i have ...
1
vote
1answer
45 views

Proving that co-finite languages can be decided in constant time

I am trying to show that given a co-finite language $A$, $A \in \text{TIME}(1)$. If $A$ is co-finite, $A$ is regular, so $A \in \text{TIME}(n)$. I'm not sure how to proceed from here. Any hints?
3
votes
2answers
95 views

Efficiently shuffling items in $N$ buckets using $O(N)$ space

I’ve run into a challenging algorithm puzzle while trying to generate a large amount of test data. The problem is as follows: We have $N$ buckets, $B_1$ through $B_N$. Each bucket $B_i$ maps to a ...
1
vote
1answer
26 views

Find Hamiltonian cycle in polynomial time

I want to know for what types of graph it is possible to find Hamiltonian cycle in polynomial time. It would be helpful also to show why on some types of graph finding Hamiltonian cycle would be only ...
0
votes
1answer
24 views

How to compare an element with other elements within an array efficiently for a condition

I need to compare each index with one another and associated array value as well. For example, ...
3
votes
0answers
15 views

Power of 2 assumption in Divide and conquer [duplicate]

Currently doing an Algorithms course in my 2nd year of university (I am a maths student, but thankfully at Warwick University, we have quite a flexible degree). One of the topics we cover is the ...
1
vote
1answer
27 views

How to calculate $\sum_{i=1}^n \mu^2(i)$ in less than $O(n)$'s time

To go with $O(n)$, we can use the linear sieve according to that $\mu(n)$ is multiplicative. But it seems that we don't have to work each $\mu(n)$ out and accumulate them together, because I only want ...
2
votes
1answer
49 views

Is this an abuse big O notation as a power of a number?

Theorem 7.11 in Introduction to the theory of computation 3rth edition says Let $t(n)$ be a function where $t(n)>n$. Then every $t(n)$ time nondeterministic single-tape Turing machine has an ...
1
vote
1answer
24 views

Matrix of a graph and computational complexity

Given a simple undirected graph with no self-loops, $G = (V,E)$, where $V = {1,2,...,n}$, an $n × n$ matrix $A$ is said to be the adjacency matrix of $G$ if $A_{i,j}$ is $1$ if $(i, j) ∈ E$ and $0$ ...
0
votes
0answers
26 views

Average runtime for search in AVL tree

The Question: Suppose there is a hash table implemented with an array of AVL trees. Assume the hash function was very bad for our data, and half of the keys got mapped to one position/bucket, and the ...
1
vote
2answers
32 views

Addition or Subtraction of Polynomials

Can addition (or subtraction) of polynomials of degree $< n$ be done in constant time ? I am quite new to algorithms. I thought about using sorted arrays for storing the coefficients. But the ...
0
votes
0answers
10 views

Determine the time complexity of code [duplicate]

I need to determine time complexity of the next code: j1=1 j2=1 for i=1 to n k=j1 while k<=j2 s=s+j k=k+1 j1=j1+2i+1 j2=j2+4i+3 return s ...
0
votes
1answer
26 views

My code works, But how do I make this code run in a deterministic time?

The Problem: Given 3 inputs Bounce, Ball drop height, and ball view height. How do I calculate the number of times the observer can see the ball pass. So my code gives correct output, but it takes ...
0
votes
0answers
16 views

What is the most accurate technique to calculate Time complexity [duplicate]

For some algorithm its really obvious (first sight) to get the time complexity, for other its bit confusion to calculate it, let me elaborate more in this example: Problem given a sorted Array in ...
-1
votes
0answers
14 views

Collect stamps, algorithm

Suppose you have a box full of stamps. There are $a$ stamps in the box. You want to get the $b$ oldest stamps from the box. Whereby $a$ is much bigger than $b$. What would be the best algorithm (worst-...
1
vote
0answers
19 views

Complexity of bisection method for finding an interval

Let $f$ be a continuous function and $[a,b]$ be an interval where $f(c)=0$ for some unique number $c \in [a,b]$ and where $f(a) f(b) \leq 0$. Suppose there exists a sub-interval $[a_0,b_0]\subset [a,b]...
2
votes
0answers
42 views

Modular reduction in a finite field

Let $\mathbb{F}_p$ be a finite field of prime order $p$. Define $r_q : \mathbb{F}_p \to \mathbb{F}_p$ as $r_q (x) = x \bmod q$ with $q<p$. A tad more formally, treat $x$ as an integer in $[0, p)$ ...
0
votes
0answers
18 views

Understanding the logic of algorithm runtime

I'm trying to understand the runtime of this code: def f(n): if (n <= 1): return 1 else return f(n-1)*f(n-1) + f(n-1) At first, my logic said ...
0
votes
0answers
15 views

What is the complexity of the following program? [duplicate]

int max = int(pow(2,n)); int sum = 0; int i ; for(i = 1; i<=max; i++) { sum++; } How do I calculate the complexity of this program? Is it O(NlogN)?
1
vote
1answer
47 views

Finding the Kth largest element can be optimized to O(n) only if k is a constant?

There's a famous question posted on this site which asks about finding the $k$th largest element. Many answers are written there which optimized it and found algorithms with expectation of $O(n)$. ...
4
votes
2answers
91 views

Is “super-exponential” a precise definition of algorithmic complexity?

I cannot seem to find a precise definition of what "super-exponential" is supposed to refer to when one's talking about an algorithm's time complexity. For instance, if an algorithm runs for $nC(n-1)$...
0
votes
0answers
41 views

Finding all subsets of a set

I have a set, and i want to find all its subsets. what is the best time complexity to find it? What is the most efficient algorithm to find all subsets of a set?
1
vote
1answer
28 views

Summation Properties of Big Omega

What are the properties of summation with Big Omega? I have been looking online but cannot find any sources on summation with Big Omega, only for Big Oh. For example, my main inquiry is if this ...
2
votes
1answer
108 views

Time complexity of a language whose alphabet has a single symbol

Consider a language $L$ such that $L \subseteq \Sigma^*$, where the cardinality of $\Sigma$ is $1$ (i.e. the alphabet has only one symbol). E.g. $L \subseteq \{a\}^*$. Can anything be said about the ...
2
votes
1answer
40 views

Maximum number of segments with no intersection [duplicate]

This is an interview question. Suppose you have an array of n segments, when each segment is a pair of two integers: start point and end point. For example: ...
1
vote
3answers
88 views

Data structure for getting the k'th largest element

I'm given a set of $n$ numbers. Is there a data structure that builds in $O(n)$ (linear time) and gets the $k$'th largest element in $O(k)$ time? Also, is there anything better than $O(k)$?
0
votes
0answers
25 views

Sieve of Eratosthenes, time and space Copmplexity

The Sieve of Eratosthenesis an algorithm generate the prime numbers, $2,3,5,7,11,13,...$ by drawing a list of numbers crossing out multiples of the smallest number in the list. what is the time and ...
1
vote
2answers
99 views

Knapsack problem: equal profits

I am looking for references to efficient algorithms that solve knapsack problem where all profits are equal. More formal definition of the problem from a Wikipedia article on KPs: If all the ...
1
vote
0answers
11 views

Time dependent scheduling with profit

I have a problem. I want to know how to solve this in polynomial time (is it possible?). There are $n$ customers that must be served by single machine. For every customer $C_i$, it has a profit $P_i =...
0
votes
1answer
26 views

Which calculating running time are correct?

Let $C$ be an array with length $n$ (assume the elements are cities with some properties). We have some properties sorted by importance. For example, 1.area, 2.population size, .... We use the ...
1
vote
2answers
50 views

Is the runtime of binary search big omega of logarithm of n?

My question is that can we say that runtime of the binary search is $\Omega(\log n)$? I know it is both $\Omega(1)$ and $O(1)$ for the best case, and $\Omega(\log n)$ and $O(\log n)$ for the worst ...
0
votes
2answers
27 views

Calculation of Inorder Traversal Complexity

I want to analyze complexity of traversing a BST. I directly thought that its complexity as $O(2^n)$ because there are two recursive cases. I mean $T(n) = constants + 2T(n-1)$. However, AFAI research ...