The algorithm-analysis tag has no usage guidance.
0
votes
1answer
77 views
Two-center algorithm to find minimum of farthest point
I'm trying to come up with an algorithm that allows me to find two vertices in an undirected, weighted graph that minimizes the distance to the farthest point.
Distance of the farthest point is ...
-2
votes
2answers
60 views
Shortest path common core(s) question
I'm not sure whether I'm using the correct terminology here. I'm trying to come up with an algorithm that let's me find a vertex in an arbitrary graph so that the vertex has minimum distance to the ...
-1
votes
2answers
76 views
What programming environments can be used to illustrate and benchmark the unoptimized space complexity of an algorithm?
What programming language along with implementation and compiler can I use to study the pure, unoptimized space complexity of an arbitrary algorithm? And what methods can I use to do so?
For example,...
0
votes
4answers
164 views
How the dividing Step in Merge Sort have Constant Time Complexity?
I am highly confuse while calculating time complexity of Merge Sort Algorithm.
Specifically on the Dividing Step.
In the dividing step we have to calculate the mid point of "n" i.e. "q = n/2".
How ...
0
votes
2answers
152 views
Loop Invariant in Recursive function
When I was reading Introduction to Algorithms (3rd edition, P188), there is
an algorithm called Tail-Recursive-QuickSort and we have to prove the correctness of this algorithm.
TAIL-RECURSIVE-...
-1
votes
3answers
96 views
Time complexity of an algorithm
What is the complexity of the following loop?
for(i=1;i<n;i=2^i)
sum+=i;
0
votes
5answers
172 views
Best approach to write on a database with two webservers
I have an architecture/performance problem.
The problem:
One voting based application with: 1 loadbalancer, 2 webservers and a database
10 candidates and 200k voting users.
There may be more than ...
1
vote
0answers
34 views
What are the methods to accurately test the accuracy of a parts of speech tagger?
I know that most of the pos tagger algorithms measure their accuracy token wise I.e. whether the token is tagged correctly or not
Some pos taggers provide sentence accuracy too. How is sentence ...
1
vote
0answers
71 views
String Pattern Matching from Lookup Table - Non-Exponential Solution?
Given the problem...
Given a String comprising of non-alhpabetical symbols, and a Lookup
Table where a subset of those symbols may equate to a single
alphabetical character, output all possible ...
2
votes
1answer
96 views
Optimizing the exponential smoothing of a big array
I have a large set of values (let's say 1M entries) where I need to apply an exponential smoothing algorithm, but only incrementing one value at a time (all others decay to zero). The trivial ...
0
votes
1answer
41 views
Search list items from other list, better way?
Today I have to search items of list from another list individually. I am just thinking about some better approach. Below is scenario described.
Lets say I have two arrays, arr1 having 100 elements (...
2
votes
4answers
621 views
What is Big-O notation for purely functional languages?
Is it still relevant?
Instead of
var result = new List<int>();
for (var i = 0; i < prev.Count; ++i)
{
result.Add(prev[i] * 2);
}
where the result.Add, prev[i], and * 2 instructions are ...
-2
votes
1answer
108 views
Unable to Solve Dynamic Programming
I had an assignment on dynamic programming due last night, but I had to turn it in unfinished because i could not understand how to solve the last problem:
The state wants to monitor traffic on a ...
-2
votes
1answer
164 views
How to find complexity of T(n) = 8T(n/2)+n^2.93(log n)^93?
I believe we have to use a variant of master theorem...can someone suggest me how to find complexity of such equation which doesn't directly fit into Masters theorem.
11
votes
2answers
481 views
Time complexity of 2^sqrt(n)
I am solving an algorithm question and my analysis is that it would run on O(2^sqrt(n)). How big is that? Does it equate to O(2^n)? Is it still non-polynomial time?
1
vote
3answers
350 views
Data structure for sorting by multiple attributes
I have a list of integer pairs. The value of this list is the sum of the maximum values of each pair.
For
(0, 5) (20, 5) (6, 8)
the value would be
5 + 20 + 8 = 33
Given a list like this, I ...
3
votes
1answer
102 views
Are these graph coloring algorithms equivalent?
Suppose you want to color the vertices of a graph in a greedy fashion, given a predetermined order of these vertices. The goal is to avoid giving two adjacent (linked by an edge) vertices the same ...
1
vote
0answers
98 views
Belman-Ford 2d array variation problem
I've got a problem with applying a Bellman-Ford algorithm to 2D Array (not to graph)
Input array has m x n dimensions:
s[1,1] s[1,2] ... s[1,n] -> Exit
s[2,1] s[2,2] ... s[2,...
2
votes
1answer
91 views
Running time of the specified Bubble Sort Algorithm
I have been working on a few algorithm questions the last few days, and one bubble sort problem in particular has been giving me headaches.
for (k=1; k <= A.length - 1; k++) { //Line 1
...
1
vote
3answers
316 views
What's the big-O complexity of this recursive algorithm?
I am following a course of Algorithms and Data Structures.
Today, my professor said the complexity of the following algorithm is 2^n.
I waited till the lesson was over, approached him and told him ...
3
votes
2answers
299 views
Big O Nested For Loop Breakdown
I understand how to get a general picture of the big O of a nested loop, but what would be the operations for each loop in a nested for loop?
If we have:
for(int i=0; i<n; i++)
{
for(int j=i+...
5
votes
3answers
1k views
Is O(log n) + O(log n) = O(n)? [duplicate]
We know that binary search takes O(log n) in Big O notation but if we need to run twice an algorithm of O(log n), would it be the same as O(n) in time complexity?
For example, if I have a method to ...
1
vote
2answers
725 views
Is the time complexity of a while loop with three pointers different than 3 nested for loops?
This program (written in ruby) finds the largest 3 numbers in an array (without sorting the array). It has a while loop with three pointers. My fist instinct, since there is only one loop is to say ...
19
votes
4answers
3k views
When speaking, how can I say that the time complexity order of an algorithm is O(N log N)?
What term can I use to describe something with O(N log N) complexity?
For example:
O(1): Constant
O(log N): Logarithmic
O(N): Linear
O(N log N): ??????
O(N2): Quadratic
O(N3): Cubic
0
votes
3answers
512 views
Best algorithm to determine whether two arrays can be the same in a circular queue
I'm trying to figure out an efficient way to determine whether two distinct arrays of the same size can be shifted to form the same circular queue. For example:
Array1 = ['A','B','C','D']
Array2 = ['...
1
vote
2answers
248 views
What is the algorithmic time complexity of this program?
I wrote a simple program in java to create and maintain Dynamic Arrays:
public class DynamicArrays {
private Integer[] input = new Integer[1];
private Integer length = 0;
private Integer ...
-3
votes
4answers
227 views
Time complexity of this loop [duplicate]
Is the time complexity for this loop O(n) or O(log n)?
for(i=0;i<n/2;i++){}
I am thinking, the time is proportional with the input size.
1
vote
3answers
540 views
Big O notation of randomness
I was thinking about inefficient algorithms based on randomness and wondered how to categorise them.
For instance. Say you wanted to generate all the numbers from 1 to N in a random order but only ...
2
votes
3answers
265 views
Close to knapsack problem?
I think that I am trying to solve a problem somewhat similar to a knapsack problem. I am not sure though.
Please see the input given below and my solution. There are three types of items and 4 ...
1
vote
1answer
3k views
Calculate Big-O for nested for loops
I found this nested loop to calculate the Big-O notation.
for(i=0;i<n;i++)
for(j=0;j<i*i;j++)
for(k=0;k<j;k++)
I got the time complexity for the algorithm with this polynomial ...
1
vote
3answers
470 views
Check distance between all elements in a list of numbers in O(n*lg(n))
I have an exercise for my algorithms and data structures class, where I basically have to implement a divide and conquer algorithm or function called check_distance to determine whether all numbers in ...
1
vote
1answer
127 views
More efficient alternative that checks if a list can be made a palindrome
I asked this question on Stackoverflow, but they told me this is the best place to ask.
For my algorithms and data structures class, I have to write an algorithm that is more efficient in the worst ...
5
votes
1answer
2k views
Compute Adjacent Pair
I was given the following problem:
Integer V lies strictly between integers U and W if U < V < W or if U > V > W.
A non-empty zero-indexed array A consisting of N integers is given.
A ...
2
votes
2answers
945 views
Estimating run time of algorithm
For instance if i have an algorithm that is O(n2) and it will run for 10 seconds for a problem size of 1000. Now if i were to double the problem size to 2000 i want to know the approximate run time in ...
1
vote
2answers
218 views
Algorithm Space and Time Complexity with Consideration for I/O (eg cache)
Is there an expression of performance for an algorithm or data structure that attempts to consider cache and other hardware concerns?
Context: in my class we're looking at binary trees and it seems ...
1
vote
1answer
259 views
Connected components of undirected graph
Suppose I have an undirected graph G with vertices v1...vn and edges. Right now it is in adjacency list representation.
For every time moment I have as input some subset of vertices that are "active" ...
-1
votes
1answer
1k views
worst case comparisons for special case insertion sort [closed]
Consider an Insertion Sort with a Sentinel on n values, where every value occurs exactly
twice in the input (so n must be even).
So the best case input for comparisons is when the elements are ...
0
votes
2answers
153 views
Time complexity analysis for recurrence relation
I was asked to figure out the time complexity analysis for the following recurrence relation
T(n) = 4*T(n-1) + c.
Basically, I did a replacement.. T(n-1) = 4 * T(n-2) + c and so on..
T(n) = 4^k T(1) ...
-2
votes
1answer
258 views
Time complexity for a recurrence relation using Divide and Conquer Master Theorem [closed]
For the recurrence relation : T(n) = 16T(n/4) + n!
I have found that the order is Θ(n!).
But I don't understand how it can be deduced using Master Theorem.
0
votes
3answers
275 views
Big-O notation for other cases
I was just reading answers to a question Plain English explanation of Big O
From that i came to know that Big-O notation is just an "upper bound" of the complexity of an algorithm?
But can we apply ...
1
vote
2answers
2k views
Lower and Upper bound of an algorithm
I am learning about analysis of algorithms.
I came across the term "upper bound" and "lower bound" in "worst-case" running time of an algorithm.
Are they applicable to only the "worst case" or can ...
0
votes
1answer
548 views
Shortest path to visit all nodes [duplicate]
I am given a set of tourist attractions(nodes identified by x, y) and i need to find the shortest path to visit them.
The way i thought of it, is i will ignore if there are streets available and ...
4
votes
3answers
180 views
Algorithm Analysis: In practice, do coefficients of higher order terms matter?
Consider an^2 + bn + c. I understand that for large n, bn and c become insignificant.
I also understand that for large n, the differences between 2n^2 and n^2 are pretty insignificant compared to the ...
5
votes
3answers
1k views
Loop runtime question
I had an exam today and I feel that I did pretty well, except I could not for the life of me figure out what appears to be an unbelievably simple question.
We were asked to give theta notation run ...
1
vote
2answers
156 views
What's the professional name for the software planning diagrams, those with ellipses and rhombuses?
What's the official name for a diagram like this one, used to structure a conditional plan.
The shapes of the objects are by convention ellipse for an action, rhombus for a question, rectangle for a ...
1
vote
1answer
302 views
Check word density within a document
Here is the situation:
I have a Document(d) and a set of keywords (Set<String> keywords). I like to check the density of each words from set keywords with d.
I have few solution but not really ...
18
votes
5answers
10k views
Algorithms: How do I sum O(n) and O(nlog(n)) together?
I have the follow algorithm which finds duplicates and removes them:
public static int numDuplicatesB(int[] arr) {
Sort.mergesort(arr);
int numDups = 0;
for (int i = 1; i < arr.length; ...
2
votes
3answers
101 views
recalculation model for GUIs
I often come across this problem.
Say to have a form with some controls:
A
B
C = A + B
D
E = C * 2 ONLY IF D==TRUE
F
G = A - F
The user fills A, then B.
The system calculates C.
The user fills D (...
0
votes
2answers
652 views
How are the tiles in WORDAMENT organized?
I'm trying to create a word game, just like WORDAMENT, in my spare time. In order to present a new round, I need to create a board with 16 letters organized in a 4*4 grid. Currently, I'm generating ...
1
vote
2answers
1k views
How to measure algorithm accuracy?
I have a few optimization algorithms (for finding function minimum) and I'd like to check how good they are. Suppose I build test cases and compare the actual results to theoretical ones.
What ...
