Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage.

learn more… | top users | synonyms

1
vote
0answers
33 views

Why is my bubble sort taking longer to sort a random array as opposed to a descending array?

I am in an entry-level algorithms class, and for our final project we are coding and thoroughly analyzing 6 different sorting methods. Part of the analyzation is timing the methods and comparing the ...
2
votes
2answers
33 views

To prove the recurrence by substitution method $T(n) = 7T(n/2) + n^2$

I have done the proof until the point when $T(n) \leq cn^{\log7}$. But when it comes to finding the value of constant $c$, I am getting stuck. The given recurrence relation is $T(n) = 7T(n/2) + ...
2
votes
1answer
25 views

Why are the two random variables independent in the analysis of Randomized Selection algorithm in CLRS?

In section 9.2 of CLRS (Introduction to Algorithms; page 185 in the 2nd edition and page 215 in the 3rd edition), a randomized selection algorithm is presented. For its analysis, $T(n)$ is a random ...
1
vote
1answer
22 views

Lower bound on number of comparisons needed to search for a number in a sorted 3-d array

Suppose we have an $N \times N \times N$ 3-d sorted array meaning that every row,column, and file is in sorted order. Searching for an element in this structure can be done using $O(N^2)$ comparisons. ...
0
votes
0answers
12 views

Analysis of Deterministic Skip Lists [on hold]

Can anyone tell me the analysis of a determinstic skip list? I read Munro's paper on Skip Lists but it was kind of difficult for me to understand.
1
vote
2answers
30 views

$T(n)=2T(n/2)+n\log n$ and the Master theorem [duplicate]

According to Introduction to algorithms by Cormen et al, $$T(n)=2T(n/2)+n\log n$$ is not case 3 of Master Theorem. Can someone explain me why? And which case of master theorem is it?
0
votes
0answers
24 views
0
votes
3answers
385 views

Why is constant always dropped from big O analysis?

Suppose I have an algorithm that has a performance of $O(n + 2)$. Here if n gets really large the 2 becomes insignificant. In this case it's perfectly clear the real performance is $O(n)$. However, ...
1
vote
0answers
25 views

Gradient descent vs. Newton's method: which is more efficient?

Using gradient descent in d dimensions to find a local minimum requires computing gradients, which is computationally much faster than Newton's method, because Newton's method requires computing both ...
1
vote
1answer
25 views

Time Complexity of Halley's Method

What is the time complexity of Halley's Method? I am thinking ${\cal O}(\log(n)F(n))$, or something very similar to Newton-Raphson, but I feel as though there should be some change to the complexity ...
2
votes
3answers
79 views

How is A* search superior to Dijkstra's algorithm

Dijkstra's algorithm is often quoted as being used to find the shortest path route however I was surprised to know that there exist A* search which is a extension of Dijkstra's algorithm. How is it ...
32
votes
2answers
2k views

Is there a system behind the magic of algorithm analysis?

There are lots of algorithm-analysis questions around. Many are similar, for instance those asking for an analysis of nested loops or divide & conquer algorithms, but most answers seem to be ...
3
votes
1answer
71 views

Unique keys in a binary search tree

I'm studying for my finals and I can across this statement. "For a fixed set of (unique) keys, any binary search tree containing those keys can be converted to any other BST on the same set of keys ...
0
votes
2answers
43 views

Why don't we calculate swaps and other steps except comparison for finding time complexity of a sorting algorithm? [duplicate]

I was learning some basic sorting techniques with their complexity. However I cannot understand why only the number of comparisons are taken into account while calculating time complexity and ...
0
votes
0answers
19 views

Uniform Binary Search explanation and lookup table [duplicate]

Please can anyone explain me the worst ,average and best case running time for the Unifrom binary search .. Also how can the lookup table be explained?
0
votes
0answers
15 views

Time complexity of complex nested for loops [duplicate]

What are the time complexities of the following code? I posted this on the general stackexchange website, but it was suggested that I post it here. ...
4
votes
2answers
187 views

Expected number of updates of minimum

I came across the following problem in a exam. We choose a permutation of n elements $[1,n]$ uniformly at random. Now a variable MIN holds the minimum value seen so far at it is defined to $\infty$ ...
5
votes
4answers
245 views

Approximating NP-complete problems

Say that for a particular problem, e.g., the independent set problem, it has been shown that no polynomial-time algorithm exists to solve it. Could we get around this by finding an algorithm which ...
1
vote
0answers
23 views

Complexity of a nested for loop [duplicate]

I'm trying to work through various exercises in Skiena's "Algorithm Design Manual." One problem that I am stuck on is as follows: What value is returned by the following function? Express your ...
2
votes
1answer
29 views

Analysis of Algorithms: Applying Concepts [duplicate]

I believe I understand the concepts of algorithm analysis. However, I'm not fully confident in applying those concepts. I'd appreciate help in bridging the gap between concept and application. I ...
3
votes
3answers
85 views

How do O and Ω relate to worst and best case?

Today we discussed in a lecture a very simple algorithm for finding an element in a sorted array using binary search. We were asked to determine its asymptotic compelxity for an array of $n$ elements. ...
1
vote
2answers
41 views

Correctness proof of greedy algorithm for 0-1 knapsack problem

We have a 0-1 knapsack in which the increasing order of items by weight is the same as the decreasing order of items by value. Design a greedy algorithm and prove that the greedy choice guarantees an ...
2
votes
2answers
55 views

Amortized Analysis for Addition of $n$ numbers

How can we add n positive integers with binary expansion $l_1$, $l_2$,...$l_n$ bits so that the total complexity is $O (\sum l_i)$ for $i = {1,...,n}$ ? More importantly, how can show this complexity ...
-1
votes
1answer
38 views

Custom binary counter supports only increment in $2^i$ values amortized analysis

I'm a having trouble analyzing this algorithm. This is a binary counter that supports only increments in $2^i$ values it's implemented in this way: starting from the $i$-th location change all the ...
0
votes
1answer
62 views

Why is there a 2n+1 comparison for a linear search algorithm?

Suppose an algorithm goes through a list of n integers and for every iteration of the loop it is needs to check if the current evaluated element of the list is even. If it is even, return the index of ...
0
votes
2answers
75 views

Calculating time complexity of two interdependent nested for loops

Consider the following code segment : for (int i = 1; i <= n; i++ ) { for (int j = 1; j <= n; j = j + i ) { printf("Hi"); } } Here, the ...
0
votes
1answer
78 views

Prim's Minimum Spanning Tree implementation $O(mn)$ or $O(m+n \log n)$?

I am reading Prim's MST for the first time and wanted to implement the fast version of it . $m$ - The number of edges in the graph $n$ - The number of vertices in the graph Here's the algorithm ...
1
vote
1answer
59 views

Recurrence of T(n) = T(n/3) + T(2n/3) [duplicate]

I've searched online for this but I only seem to find answers for a similar equation: T(n) = T(n/3) + T(2n/3) + cn But the one I'm trying to solve is: ...
3
votes
3answers
94 views

How to implement graph search to solve Sudoku puzzle

My teacher pointed out to us during lectures that we could use Graph Search to help us solve Sudoku puzzles which has left me puzzled . I dont see how this is possible as Graph Search is mostly ...
0
votes
0answers
66 views

Why is Big $O(X^3)$ instead of Big $O(X^2)$ for this algorithm [duplicate]

The is the running time of an algorithm : $0.5 X^2 + 3X$ , Q1) i dont understand why my lecturer says that the Big O is $O(X^3)$, shouldnt it be $O(X^2)$ as it is bounded by the quadratic power of ...
2
votes
0answers
24 views

How do you compare algorithms based on scaling of their cache misses?

We all know how to use “Big O” notation to show how CPU instructions run increase as the size of the dataset increases. E.g. a quick sort is O(n log n). However for the last few years, ...
-1
votes
1answer
36 views

What's the time complexity of this append method? [closed]

I made a method that appends a sequence to another sequence. So: (append [1,2,3] [4,5,6]) = [1,2,3,4,5,6] CODE In C# ...
-1
votes
1answer
43 views

Examples of algorithms that have runtime O(N + M) resp O(NM)

I'm looking for examples of loops that have running time $O(nm)$, $O(n+m)$ and $O(n\log m)$ to help me understand these concepts. Could anybody give some examples and explain why they have the given ...
0
votes
1answer
31 views

Binary counter amortized analysis [closed]

This is a question I have stumbled upon in my textbook, and didn't really know how to approach: Given a $k$-bit binary counter. We have an operation Increment, which adds 1 to the counter. We add a ...
1
vote
0answers
28 views

Shamos-Hoey Line segment intersection runtime

In the Shamos-Hoey algorithm for finding whether or not any two of $n$ line segments intersect, which is available at this site: http://geomalgorithms.com/a09-_intersect-3.html, there is use of ...
0
votes
1answer
127 views

Impact on the order of elements on the cost of searching in a linked list

I have the following homework question that I am struggling with. I have read the corresponding chapter from the book, but no guidance there. Consider a linked list $X: X_1 \to X_2 \to X_3 \ldots$. ...
0
votes
0answers
33 views

O(pattern_length) failure function in kmp algorithm

consider the pseudo code for calculating failure function: I partial understand the algorithm. KNUTH-MORRIS-PRATT FAILURE (P) Input: Pattern with m characters Output: Failure function f for P[i . ...
0
votes
1answer
19 views

The number of executions of the count statement; how many?

How many times does the statement count in line 5 executes in terms of $n$? ...
3
votes
4answers
53 views

Asymptotic Runtime of Interrelated Functions

I have two functions $S$ and $T$ which are interrelated and I want to find the asymptotic worst case runtime. The fact that they are interrelated is stumping me... How would I find the asymptotic ...
-1
votes
2answers
75 views

How to find the cost of pseudocode with a nested loop and a nested if statement?

How can I find the cost of pseudocode with a nested loop and a nested if statement? On the left hand side is an example from a textbook I am following. On the right hand side is pseudo code that I ...
2
votes
1answer
84 views

How can we minimize the total distance of cross pairs in an array

Suppose we had 2 arrays of the same size with positive numbers and we wanted to pair up the elements of each array such that the total difference between the pairs is minimized. The first thought ...
2
votes
1answer
49 views

Time complexity of proximity search in distance matrix

I am a high school student computationally studying the 3-dimensional structure of chromosomes by 40 kilobase loci. In a nutshell, loci that are close in space tend to express their genes at the same ...
0
votes
3answers
66 views

Big O relation between $2^n$ and $2^{2n}$

I know that: If $f(n) = O(g(n))$ , then there are constants $M$ and $x_0$ , such that $f(n) <= M*g(n), \forall n > n_0$ The other, plain English way of defining it is, If $f(n)=O(g(n))$ ...
6
votes
1answer
162 views

Why is this function computable in $O(n^{1.5})$ time?

My textbook says: "We define the function $f\colon \mathbb{N}\to\mathbb{N}$ as follows: $f(1)=2$ and $f(i+1)=2^{f(i)^{1.2}}$. Note that given $n$, we can easily find in $O(n^{1.5})$ time the number ...
3
votes
1answer
64 views

Algorithm Analysis: Expected Running Time of Recursive Function Based on a RNG

I am somewhat confused with the running time analysis of a program here which has recursive calls which depend on a RNG. (Randomly Generated Number) Let's begin with the pseudo-code, and then I will ...
0
votes
0answers
18 views

Recurrence relation help? [duplicate]

$$t(n)=\begin{cases}n&\text{if }n=0,1,2,\text{ or }3\\t(n-1)+t(n-3)-t(n-4)&\text{otherwise.}\end{cases} $$ Express your answer as simply using the theta notation. I don't know where to go ...
0
votes
0answers
16 views

Can someone help solve recurrence relation? [duplicate]

It says to solve the recurrence exactly for n a power of 2. T(n) = {1}, if n = 1 T(n) = {5T(n/2) + (n lg n)^2, otherwise ...
1
vote
2answers
40 views

Are loop counters spatially or temporally local?

Consider this nested loop: for (i=0 to n) for(j=0 to n) for (k=0 to n) sum := sum +k end for end for end for Do ...
1
vote
1answer
56 views
4
votes
1answer
92 views

Which computational model is used to analyse the runtime of matrix multiplication algorithms?

Although I have already learned something about the asymptotic runtimes of matrix multiplication algorithms (Strassen's algorithm and similar things), I have never found any explicit and satisfactory ...