# Tagged Questions

The tag has no usage guidance.

26 views

### Which database to use for real time data update for trading and analysis? [closed]

I am thinking about a website for trading and analytics. I am thinking which technologies can be used for this kind of website and so I have doubt with database. Which database is suitable for a ...
295 views

I have a problem I am developing a solution for and currently I solve it with a brute force solution that checks all possibilities. It works for small numbers of bins but I'd like to work with a ...
544 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 ...
176 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 ...
87 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 ...
66 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] ... ...
2k views

### A* Algorithm Completeness Proof

The A* Algorithm is the optimal (provided the heuristic function is underestimated), complete & admissible (provided some conditions). I know the proofs of admissibility & optimality. But how ...
67 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 ...
224 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 ...
187 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 ...
551 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 ...
587 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 ...
130 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) ...
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
10k views

### Finding the time complexity of the following program that uses recursion

I need to find the time complexity in terms of Big Oh notation for the following program which computes the factorial of a given number: The program goes like this: public int fact(int n){ if (n ...
198 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 ...
290 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 = ...
318 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 ...
177 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.
188 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 ...
535 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 ...
246 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 ...
1k views

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 ...
1k 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 ...
170 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 ...
108 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 ...
272 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 ...
197 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" ...
607 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 ...
11k views

### Why is binary search,which needs sorted data, considered better than linear search?

I have always heard that linear search is a naive approach and binary search is better than it in performance due to better asymptotic complexity. But I never understood why is it better than linear ...
153 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.
225 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 ...
1k 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 ...
377 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 ...
163 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 ...
644 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 ...
1k views

I have an ArrayList<LinkedHashSet<String>> setOfStrings for example this arraylist internally is composed like: positionX[hello,car,three,hotel,beach] positionY[.....] ... I want to ...
1k views

### Space complexity of Iterative Deepening DFS

We read on Wikipedia > Iterative deepening depth-first search that The space complexity of IDDFS is O(bd), where b is the branching factor and d is the depth of shallowest goal. Wikipedia also ...
131 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 ...
7k 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; ...
232 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 ...
96 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 ...
4k views

### Divide and Conquer algorithms – Why not split in more parts than two?

In divide and conquer algorithms such as quicksort and mergesort, the input is usually (at least in introductory texts) split in two, and the two smaller data sets are then dealt with recursively. It ...
241 views

### Sentence Tree v/s Words List

I was recently tasked with building a Name Entity Recognizer as part of a project. The objective was to parse a given sentence and come up with all the possible combinations of the entities. One ...
152 views

### How to avoid or minimise use of check/conditional statement in my scenario?

I have scenario, where I got stream and I need to check for some value. If I got any new value I have to store it in any of data structure. It seems very easy, I can place conditional statement ...
325 views

### Approach for packing 2D shapes while minimizing total enclosing area

Not sure on my tags for this question, but in short .... I need to solve a problem of packing industrial parts into crates while minimizing total containing area. These parts are motors, or pumps, ...
1k views

### How meaningful is the Big-O time complexity of an algorithm?

Programmers often talk about the time complexity of an algorithm, e.g. O(log n) or O(n^2). Time complexity classifications are made as the input size goes to infinity, but ironically infinite input ...
340 views

### How to approach program design with respect to data strucutres and algorimths - is there an equivelant of the OO design process for d.s.'s + algs? [closed]

My applogies for probably the worst written body of text I have produced in my life and many thanks to those willing to plough through it all. I was (and still am) not able to clearly express what I ...