# Questions tagged [runtime-analysis]

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

797 questions
Filter by
Sorted by
Tagged with
55 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?...
114 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 ...
97 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 ...
29 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 ...
2k views

### What is a computer year?

In one of the text book its mentioned that 'running time of this algorithm is 200 computer years'. Can somebody please explain what is the meaning of a computer year?
389 views

### Big-O notation for nested loops that might skip iterations

When you have an algorithm that may skip a lot of iterations due to a hash table lookup, do you still count the iterations that are exited immediately? Hypothetical example: ...
229 views

### Finding time complexity when while loop included [duplicate]

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. Example 1: nums1 = [1, 3] nums2 =  The median is 2.0 Example 2: nums1 = [1, ...
39 views

### The time complexity of the Wikipedia version of Pollards $(p-1)$ algorithm

I am trying to understand the runtime of Pollard's $(p-1)$-algorithm as presented on Wikipedia. There the author writes that it takes $\mathcal{O}(B\log B\log^2n)$ time, but I do not see why. Here ...
23 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 ...
88 views

...
1k views

### Complexity of finding a majority element

I was given a question that is stated that; Suppose you’re consulting for a bank that’s concerned about fraud detection, and they come to you with the following problem. They have a collection ...
27 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 ...
153 views

### Tail recursion can't work with dynamic programming programs

I am doing some exercises on dynamic programming in order to get familar with this concept. I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic ...
113 views

### minimum number of nodes that traverse all the graph

In the following graph, we can traverse entire graph if we select the nodes 0 and 2. I am looking for an efficient algorithm which returns this two nodes. Note that this is neither vertex-cover ...
152 views

### Is there an example of Dinitz's algorithm running with the worst time complexity?

I am trying to find a network, where Dinic's algorithm makes $|V|^2*|E|$ steps. Clearly it cannot be a network with $3$ or less vertices, but I am not able to come up with a working example for quite ...
51 views

### Finding loop invariant of Lowest common multiple function

So I have the following function: ...
62 views

### Upper bound on the average-case runtime of shell sort

I found that shell sort with the gaps of Fibonacci sequence has the lower bound complexity $\Omega(N \log N)$ in average cases. I want to know the upper bound complexity in average cases, so I write ...
1k 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)$...
147 views

### Is my algorithm a $O(nm \lg m)$ solution for sorting a row and columnwise sorted $2D$ array?

The problem (from MIT 6.006 course) is the following: In this problem, you are given a $2D$ array of integers $A$ that has $n$ rows and $m$ columns. (Assume $m$ is much (e.g., exponentially) ...
234 views

356 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 ...
62 views

### What is the Big-O runtime of this algorithm? [duplicate]

Can anyone explain why the runtime of this is in O(N^3)? Additionally, what would the run-time be in Big-OH if the else statement was removed. ...
387 views

### Help with deterministic selection algorithm

All we know what is Deterministic Selection Algorithm: Line up elements in groups of five (this number $5$ is not important, it could be e.g. $7$ without changing the algorithm much). Call each group ...
29 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 ...
58 views

### What does ∈ mean in the exponent?

I'm having troubles understanding the following proof:  \begin{align*} &\text{Proof: } \forall \epsilon \in \mathbb{R}^+, \forall a \in \mathbb{Z}^+, n^\epsilon \gg \log_a(n) \\ &\...
305 views

### Finding recurrence equation for a variant of insertion sort [closed]

I have a variant of Insertion sort (recursive version) that we call split insertion sort because there are two kinds of input. The input array has both numbers and alphabets, hence we have to sort ...
75 views

### Optimizing coin splitting - Is this algorithm as fast as I think?

In a recent exam, I've been asked to solve the following problem: The problem Two players play the following game: Given a sequence of coin values $v_1,\ldots,v_n (n \vert 2)$ the players ...
32 views

### Theta bound of the following function [duplicate]

Suppose the function $f(n)$ is defined as the number of $\ast$ printed in the following code ...
2k views

### What's the Big O runtime of a DFS word search through a matrix?

The problem is to try and find a word in a 2D matrix of characters: Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent ...
### What is the complexity of checking whether an integer $n \geq 2$ is expressible in the form $a^b$ where $a, b \in \mathbb{N}$?
In Concrete Mathematics Textbook by Donald Knuth and Oren Patashnik , ch.2 Sum ,sec2.2 He wrote: The average number of comparison steps made by quicksort when it's applied to $n$ items in random ...