Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage. Use the [runtime-analysis] tag for questions about the runtime of algorithms.

learn more… | top users | synonyms

-2
votes
1answer
14 views

Complexity and number of bits of square root number

Let an integer a, and b is the number of bits a. 1) If I have a number ...
-1
votes
1answer
19 views

Time complexity for Breadth-First search

I would like to know why the average number of nodes at level d in BFS in a search tree is $\frac{1+b^d}{2}$ as given in this lecture(p.15)?(Here b is the branching factor of the tree and d is the ...
1
vote
0answers
16 views

Wald's equation for dependent decrements

I'm taking a course on Coursera about approximation algorithms for fun and one of the modules uses probability to analyze the cost of a linear program with randomized rounding solution to the set ...
2
votes
1answer
27 views

Linearity of Expectation

I'm taking a course on Coursera about approximation algorithms for fun and one of the modules uses probability to analyze the cost of a linear program with randomized rounding solution to the set ...
0
votes
2answers
45 views

Generally, does the time it takes to compute (n mod m) depend on the size of n?

Example: Suppose I have a number a with 100 decimal digits, b with 200 decimal digits, and m with 10 decimal digits. Would the speed of the computation a mod m vary greatly from b mod m because of ...
3
votes
4answers
614 views

Is there a meaningful difference between $O(1)$ and $O(\log n)$?

A computer can only process numbers smaller than say $2^{64}$ in a single operation, so even an $O(1)$ algorithm only takes constant time if $n<2^{64}$. If I somehow had an array of $2^{1000}$ ...
2
votes
0answers
26 views

Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?

I am experimenting with the sorting of arrays and their execution times. While using bubblesort, insertsort and ...
-1
votes
0answers
20 views

Runtime complexity for selection sort using recursion [duplicate]

I have implemented selection sort using recursion for which I am getting following function for var inputArr = [99,88,77,66,55,44,33,22,11,10]; $(-1 + (-1)^n + 8 n ...
3
votes
1answer
40 views

Why does merging two sorted arrays take 2N - 1 comparisons?

A friend of mine asked me a question on how to prove that merging two sorted arrays requires at least 2N - 1 comparisons Prove that merging two sorted arrays of N items requires at least 2N-1 ...
0
votes
1answer
30 views

Understanding Jeff Erickson's analysis of a basic tree traversal algorithm

I have trying to understand graph algorithms from scratch and I have explored various resources but the most understandable for me was these lecture notes Algorithms. The way professor teaches seems ...
0
votes
1answer
29 views

Difference between factorization prime numbers with limited number of bits and without limit [closed]

I have a function that attemps to factor a number. int factor(int n) { for (int p = 2; p < sqrt(n); p++) { if (n % p == 0) return p; } return -1; } ...
0
votes
0answers
19 views
-2
votes
1answer
66 views

What is the time complexity of the nested loop ($j=i \ldots n$ inside $i=1 \ldots n$)? [duplicate]

I am looking for the time complexity of the following nested loops, where the inner loop is shrinking. ...
0
votes
1answer
27 views

Runtime analysis with recursion factor

I have this code: if n is even { for i=1....n for j=1...i print j return 8*foo(n/2) } Asking to calculate the running time $T (n)$. I thought at first ...
3
votes
1answer
39 views

Recurrence: space complexity to Tournament Method

Tournament method have this structure to found min and max (function getMinMax): ...
0
votes
1answer
36 views

Space complexity of Horner's method

Following is the excerpt from wiki If numerical data are represented in terms of digits (or bits), then the naive algorithm also entails storing approximately $2n$ times the number of ...
3
votes
2answers
85 views

Why do we use big O rather than $\Omega$ when discussing best case runtime?

When discussing the worst case runtime $T(n)$ of an algorithm, we attempt to bound $T(n)$ above by some simple function $g(n)$, so that $T(n) = O(g(n))$. When discussing the best case runtime $T(n)$ ...
0
votes
0answers
43 views

Calculating Big-O

I was asked to find the O-complexity of the algorithm accepting the language {0^(2^k) | k>=0} meaning the length of a string in the language will be of a power of two. (using a turing machine) $ The ...
3
votes
1answer
63 views

When would the worst case for Huffman coding occur?

I am doing a project on Huffman coding and wanted to know when it wouldn't be ideal to use or rather when would the Huffman coding produce low compression. Since it mainly revolves around the ...
1
vote
0answers
21 views

Analysis of Weighted Quick Union with Path Compression

I have searched the internet for an analysis of why WQUPC is amortized $O( m \alpha (n) ) $ for m operations on n nodes ( $\alpha ( n) $ is the inverse Ackerman function). I understand why it is $O ( ...
-3
votes
0answers
8 views

complexity of incrementally creating a graph [duplicate]

What is the complexity of the two functions f() and g()? They both build a graph G(V, E) incrementally, I think that they are both O(|V|)? f(n): 1. start with an initial graph K3 (triangle); 2. for ...
1
vote
1answer
18 views

Algorithm to convert rendered number back into symbolic form

If you have a number such as $3.14626437$ and you need to know what symbols create it, as far as I know, there are two tools: 1- ISC 2- wolframalpha and the answer is $\sqrt2+\sqrt3$ I am ...
0
votes
1answer
40 views

Are all problems approached and solved in fundamentally the same way?

This question might be a bit to vague, not make sense, or not developed enough yet to ask, but I thought I might give it a shot. This questions stems from a conversation a friend and I were having ...
0
votes
2answers
57 views

Question about time-complexity for MST-like algorithm

I have got a problem with an excercise about graphs: Your friend has been hired by a brewery to work out the most efficient delivery route for the beer-delivery truck drivers. A typical delivery has ...
2
votes
1answer
87 views

Can RadixSort be Ω(n log n)?

I read about RadixSort and its time complexity and the worst best and average time Complexity is O(n) , so my question is can radixSort be Ω(n log n)?
0
votes
2answers
84 views

What is the time complexity of this algorithm?

In my class my teacher calculated the time complexity for this algorithm, relative to the number of sum operations executed: She represented the cost of the algorithm by the following sum: ...
1
vote
2answers
60 views

Let a > 0 be a constant. Find a simplified, asymptotically tight bound for the recurrence T(n) = aT(n-2) + C

So I have read the posts on this site involving recurrence relations, however this problem is a little different, because of the constant a involved with the recursive portion. I'm trying to solve ...
1
vote
0answers
96 views

When does Branch and Bound exactly stop giving solutions for the bin packing problem

I wrote a branch and bound algorithm for the bin packing problem and now I would like to know when exactly it stops giving solutions in a polynomial time. I have N items (each item i has a volume ...
5
votes
1answer
71 views

A* graph search time-complexity

Some confusion about time-complexity and A*. According to A* Wiki the time-complexity is exponential in the depth of the solution (shortest path): The time complexity of A* depends on the ...
3
votes
2answers
102 views

What is running time of an algorithm?

What do we mean by running time of algorithms? when we say running time of bubble sort is O($n^2$), what are we implying? Is it possible to find the approximate time in minutes/seconds from the ...
1
vote
0answers
58 views

Calculating number of operations in a divide and conquer approach when the input is not an exact power of 2

Here is a divide and conquer approach for finding minimum and maximum elements in an array. ...
8
votes
1answer
64 views

What is the complexity of a bracketed search using mediants?

I'm trying to estimate the complexity of an algorithm I've written for the Reko decompiler, where I'm trying to "undo" the tranformation done by a compiler to an integer division by a constant $x / ...
0
votes
1answer
40 views

Showing that an algorithm is 2-approximation

I'm having trouble showing that this algorithm is 2-approx. We are given a set P of n points on the plane, and a positive integer k. We want to partition these points into k sets such that the ...
3
votes
2answers
509 views

How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms?

How are asymptotical time complexities calculated for recursive algorithms? Recursive algorithms call themselves and therefore take up more space compared to non-recursive algorithms. But are they ...
2
votes
1answer
48 views

Costs of updating arrays to contain only zeroes

To initialize an array of length $n$ has complexity $O(n)$, as far as I understand. If I set every element to zero (with one code line), does that have time complexity $O(n)$ also? And in that case, ...
1
vote
2answers
42 views
4
votes
1answer
37 views

What to infer about maximum height of AVL tree from these three different formulae

I have came across following problem: What is the maximum height of any AVL-tree with 7 nodes? The recurrence giving number of nodes $n$ in the AVL tree for given height $h$ is as follows: ...
0
votes
2answers
67 views

What is the asymptotic running time of the following piece of code? [duplicate]

I am working with this problem: What is the asymptotic running time of the following piece of code? ...
5
votes
1answer
57 views

How to find time complexity for functions in lazy functional languages?

So far, I have looked around the internet for information how to find the time complexity for functions in lazy functional languages, but most of the resources on time complexity focus on strict ...
1
vote
0answers
45 views

Runnig time analysis for algorithem that merges $k$ sorted arrays to one sorted array

Given $k$ sorted arrays, the size of each array is $n$ and we want to sort them to one sorted array. assume that $k=2^p$ i.e $k\in\{ 2^1,2^2,2^3,2^4,\dots\}$ I the first step we will merge ...
4
votes
1answer
52 views

Summation of a Random Variable

I'm having trouble grokking Cormen's Algorithms book on pg. 120. The context is the hiring problem (as it is called in the book). Here is the part that is tripping me up: "Let X be the random ...
0
votes
0answers
31 views

Frequency count of while loop [duplicate]

I'm task to solve a problem in UVA and its problem 305 in particular well its easy to program it just brute forcing stuff. Part of the task is to find the big Oh of the program using frequency count ...
1
vote
1answer
85 views

How to find longest recurring pattern from lage string data set?

I need to find the substring that is from a 100,000 characters this substring must be most repeated and it need to be longest substring for example ...
2
votes
1answer
114 views

Does my simple, static hash table have O(1) worst case lookup?

Will the following simple hash table construction algorithm be able to construct a static hash table in $O(n)$ expected time, and will the worst case access time be $O(1)$? If not, what are the ...
0
votes
0answers
35 views

Is this sorting algorithm valid and able to run in O(range of input set) time?

I imagined a sorting algorithm that sorts an array in O(r) time, where r is the range. Is this already an algorithm (if so, which?), or have I made a mistake calculating the running time (probably). ...
0
votes
0answers
26 views

How do I make the “+2” go away in the recurrence relation of T(n) = 4T(n/2 + 2) + n [duplicate]

$T(n) = 4T(n/2 + 2) + n$ How can I make the plus 2 disappear? I have been reading the answer to this and I'm having trouble understanding it. Can someone maybe show me step by step how I would do ...
3
votes
3answers
397 views

Are there adversarial inputs for randomized quicksort?

Someone recently claimed that there's an adversarial input for randomized quicksort; he referenced this paper. This defies my intuition because there are results that say that randomized quicksort ...
0
votes
2answers
395 views

how to calculate time complexity of non terminating loops

I'm studying about data structures and algorithms in that Time complexity and calculating time complexity of the programs. I just wondered that how to calculate time complexity of non terminating ...
3
votes
1answer
59 views

Explanation of a simple algorithm's Big O complexity

I'm looking at a past paper, where there is the following Algorithm, and we are asked to give the runtime in O notation: ...