# Questions tagged [runtime-analysis]

Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.

835 questions
Filter by
Sorted by
Tagged with
240 views

### 3 * O(n^2) vs O(n^3)

Currently while I was coding, I got a doubt. While I was solving a particular type of problem I found it to be solved in $O(n^3)$. I have broken that problem and solved it in $O(n^2)$. But to ...
19 views

### Run time of pseudo code in big theta notation [duplicate]

I am looking for the run time of the following pseudo code. ...
206 views

### Worst Case Scenario for Quicksort algorithm with pivot element n/2

What would the worst case array look like if I decide to always take the element on the position $\frac{n}{2}$ as the pivot element? I know that if I choose the left or rightmost element as pivot ,the ...
88 views

### Is purely functional programming in some situations less efficient than imperative programming?

I am used to implementing algorithms in imperative languages. Many of the algorithms I have implemented use hash maps, hash sets, mutable arrays, heaps, doubly linked lists, etc. I understand that ...
550 views

### All superlinear runtime algorithms are asymptotically equivalent to convex function?

Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$? All the examples that I could think of satisfy the above ...
15 views

### Why does the knapsack dynamic programming solution has runtime of O(nW)? [duplicate]

Can you please help me analyse the runtime of the knapsack dynamic programming (which i have seen somewhere is O(nW))? This is the algorithm i an using: Define M[i,s] to be the maximum value that ...
151 views

### Big Oh Time Complexity Involving 'for i in range(n)' [closed]

Given the code below and the comment analysis: ...
500 views

### Complexity of many constant time steps with occasional logarithmic steps

I have a data structure that can perform a task $T$ in constant time, $O(1)$. However, every $k$th invocation requires $O(\log{n})$, where $k$ is constant. Is it possible for this task to ever take ...
47 views

### Worst Case Analysis of a Multivariate Recurrence of a Graph Algorithm

I have a graph algorithm that runs in:  T(n, m) = \begin{cases} c_1 & n \leq 2 \lor m = 1\\ T(n - i,\ m - j - k) + T(i, k) + c_2 m + c_3 n & m \leq (n-i)i\\ T(n - i,\ m) + T(i, m) + ...
61 views

### Does my solution converge to O(N) for worst-case time complexity?

Forgive me if this should be in StackOverflow or Mathematics instead! I was given the following question at an interview: ...
36 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 ...
45 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 ...
281 views

### Is there a useful algorithm with a decreasing asymptotic time?

Algorithmic complexity is usually increasing and almost always strictly increasing based on input size. This is logical since algorithms take time to execute steps, and for almost all problems, the ...
78 views

### How to find big-O for an in-place perfect shuffle algorithm

I've found a simple algorithm to interleave two halves of an array in place. It involves swapping the first 1/2 of the items into the correct place, then unscrambling the permutation of the 1/4 of ...
116 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, ...
45 views

### Mergable heap with no key knowledge cannot EXTRACT-MIN in $o(\log n)$ amortized time

We are looking into Fibonacci heaps in class at the moment, but I am stuck with this problem. Let $H$ be a mergable heap structure, by which is meant a data structure, where each element has a key, ...
145 views

### What is the asymptotic complexity of the following code snippet?

for (i = 2; i < n; i = i * i) { for (j = 1; j < i / 2; j = j + 1) { sum = sum + 1; } } I know that the outer loop can run for a maximum of $n^2$ ...
529 views

### How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?

How to find the big o running time if the recursion function have different cases of recursion with different fraction of n? If I have a recursive function like this for example (This is just an ...
44 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 ...
31 views

### Optimal scalability of a distributed algorithm

What's the optimal scalability of some algorithm when I implement it in a distributed manner? Intuitively, it seems to me that any algorithm can scale at most linearly with number of computing nodes....
49 views

### Highest stack of rectangles

Suppose we have a set of $n$ dimensional rectangles $R = \{(x_{i,1}, \ldots, x_{i,n}), i \in 1 \ldots k\}$. We want to create the highest stack in say the first dimension such that each side of the ...
664 views

### Time complexity of Dijkstra's algorithm for sparse graph

I'm not sure I understand the answer to this question: Question 9. What is the running time of Dijkstra's algorithm in a graph that is sufficently sparse - in particular, $E=o(V^2/\log V)$, ...
485 views

### Why aren't primality tests easily linear in time complexity?

Why don't we consider them as linear? I don't understand. You just have to check for factorization up to sqrt of n. So it's even faster than linear. I assume it's not linear only if we compare the ...
54 views

### Euclidean algorithm and well define ness on the underlying set

Euclidean algorithm is given below: gcd($a$,$b$):   if $a=0$, return $b$   otherwise, return gcd($b \bmod a$, $a$) Let us first argue that the algorithm terminates. The reason ...
56 views

### Finding runtime of a recurrence relation with a fractional power

Consider the following algorithm and find the tightest Big-$O$: Assume $\texttt{multiplyKS}$($A,B$) is $O(n^{1.58})$ and $\texttt{Add}($A,B$)$ is $O(n)$. If my runtime is $T(n)$, I have: Lines 1 ...
47 views

### Heap operating in time $\Gamma^{-1}(n)^2$

I have a priority queue implementation which I claim has the following worst case asymptotic run-times for the given operations: PEEK_MIN …………………………… O(1) POP_MIN…………………………… O( (INVERSE_Γ(n)) ^2). ...
188 views

### Run-time of Hungarian algorithm - matrix formulation

There are many different explanations of the Hungarian algorithm. My favorite explanation is the one based on matrices, for example here, since it is very intuitive and easy to carry out in a ...
112 views

### What would be the big-o time complexity of this scenario? [duplicate]

I am wondering what the time complexity of a for loop that increments the control variable, but also multiplies it inside the loop. For example ...
58 views

### Djikstra algorithm analysis

My textbook says that the Dijkstra algorithm's runtime is $O(n) + O(m \log(n)) = O((n+m) \log(n))$. How did they come up with that? Dijkstra algorithm pseudocode: ...
115 views

### Running Time of Sorting Algorithm

Determine the asymptotic running time of the sorting algorithm maxSort. Algorithm maxSort(A) Input: An integer array A Output: Array A sorted in non-decreasing order ...
195 views

### Running Time for Finding Maximum

Consider the algorithm findMax that finds the maximum entry in an integer array. Algorithm findMax($A$) Input: An integer array $A$ Output: The maximum entry of $A$ ...
73 views

27 views

### Why $xx^TM$ requires $O(dk)$ operations?

Suppose $x \in \mathbb{R}^d$ and $M \in \mathbb{R}^{d \times k}$. Why $xx^TM$ requires $O(dk)$ operations?
45 views

### How do you find set of keywords present in set of words in linear time or log time?

I am trying to optimize a program, where I need to know whether a given set of keywords present in the set of words. I believe using the dictionary is the only way to optimize it. Any other technique ...
89 views

### Show that the following algorithm takes $O(n)$ time

You are given a linked list of size $n$. An element can be accessed from the start of the list or the end of the list. The cost to access any location is $\min(i,n-i)$, if the location being accessed ...
65 views

### Least number of guesses needed to determine all unknown subsets of a set

Say I have a set $\mathbb{S}=\{1,2,...,n\}$. I have an adversary who breaks up $\mathbb{S}$ into $k$ unknown and disjoint subsets. Denote this new set $\mathbb{A}$. I can guess any combination $s$ and ...
49 views

### What will be big O complexity for this loop? [duplicate]

I am not able to understand time complexity of this for loop. While outer loop is O(n) the inner loop jumps certain calculation. How to find the complexity? ...
92 views

### Worst case lower bound of binary search

For the question below, it is asking to prove the lower bound on the worst case is log(n). I have no problem proving this and the solution makes 100% sense to me. However, there is a comment at the ...
87 views

### Time complexity dependent on magnitude of input [duplicate]

I'm trying to analyze an algorithm that looks like this: def foo(L): for n in L: for x in range(n): ... What would be its time complexity?...
361 views

### Find the efficiency class

I have to find the efficiency class of this algorithm b = 3 a = 4 for i = 4 to n^2 if (i mod 2 == 0) a = a+2 else b = b*3 end for I ...
144 views

### Big O understanding given different input sizes

I have a question about big O notation. Let's say I have 3 algorithms which, for an input of size $n$, have time complexity $O(n)$, $O(n^2)$ and $O(n \log n)$, respectively. Assume that all 3 ...
42 views

### A hangman variation: determining a string by guessing substrings contained in it

I came up with this Hangman variation, where you must figure out the hidden word by asking whether a string is a substring of this word. E.g. if the hidden word is "abracadabra" and I guess "cad" I ...