Complexity deals with various forms of calculating the complexity of code. Cyclomatic complexity, n-path complexity, Big O time and space complexity.
-1
votes
0answers
43 views
Algorithm for a matter of chance game
I started developing an algorithm for a matter of chance game with the following rules:
At the start of the game, the player starts on the starting case S(Start).
He starts by rolling the dice and ...
2
votes
0answers
92 views
Algorithm to find region with least-probable density
Consider the following boolean array where dark == true:
In this scenario the probability that a cell is dark or light is 50/50, but this may not be true for the general case.
Maximizing only on ...
3
votes
1answer
135 views
Algorithms comparison and complexity
I want to sole this problem:
Write a method to return all valid combinations of n-pairs of
parentheses.
The method should return an ArrayList of strings, in which each string
represents a ...
1
vote
2answers
94 views
Evaluating the cost of a query in database
We are working on a project using Google App Engine + Google Cloud Datastore. The language used is Python.
At some points of our API, we check if some arg is passed in request, and we make some query ...
1
vote
2answers
140 views
What is name of this type of complexity?
What is complexity related to number of operations/interactions between objects within a system? as that number increases the programmer capability of understanding and maintaining the system degrade.
1
vote
3answers
267 views
Find if any pair exists in an unsorted array?
I have come across a programming question in which I have to determine :
Does there exists at least one pair in a given unsorted array such
that
|i - j| <= K and |A[i] - A[j]| <= x
?
...
0
votes
4answers
178 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 ...
2
votes
7answers
423 views
Do we really need efficient algorithms? [duplicate]
I'd like to ask why people devote their time to research algorithms and their efficiency so extensively when computers nowadays are so fast.
Trying to come up with an answer I thought that maybe my ...
-1
votes
3answers
103 views
Time complexity of an algorithm [closed]
What is the complexity of the following loop?
for(i=1;i<n;i=2^i)
sum+=i;
-3
votes
3answers
220 views
inheritance and polymorphism decrease readability
Most of financial apps have complex calculations and over time have change in calculation methods. Then you mostly create a new version for your calculator class that extends previous calculator and ...
1
vote
1answer
106 views
Big-O notation and halting problems
I'm trying to understand why it's impossible to create a tool that calculates Big-O notation automatically.
I have read about Halting problems, but not related on Big-O notation and I was wondering, ...
-1
votes
1answer
38 views
Time complexity Computation
What will be the result of the time complexity of this piece of code i.e.
int sum(int A[], int n)
{
int sum = 0, i;
for(i = 0; i < n; i++) {
sum = sum + A[i];
}
...
2
votes
2answers
90 views
how to program a lookup table of input and output variables
This is a small C++ application (and the table is not huge either) so if possible I would like to avoid include anything other than STL (and boost).
So to the problem:
I have a table of predefined ...
2
votes
1answer
65 views
How do I determine correctness of a codes complexity?
Given a piece of code, I may use one of many methods to determine the big O complexity of the code manually (runtime and memory).
But, for a given piece of code, how do I determine whether what I ...
0
votes
1answer
89 views
Trying to find time complexity of modulus algorithm
I can't quite figure out the time complexity of this algorithm I've written for finding the modulo. I've added it here in psuedocode.
Modulo(int x, int n)
// x is the dividend, n is the divisor
e ...
0
votes
0answers
73 views
Dynamic programming vs branch-and-bound for the knapsack problem
I have to implement a program that solves the 0-1 knapsack problem, where the weights and values of all items are nonnegative integers.
We went over two methods in class: dynamic algorithms (...
0
votes
1answer
57 views
How to calculate big O notation according to number width?
I'm trying to understand big O with the bitwise operations. I have 2 functions those are solving the same question from different perspective.
num1BitsSecondSolution starts to shift the number right ...
0
votes
0answers
78 views
Algorithm and time-complexity of creating a sports schedule
With the NFL schedule being released last night, I started thinking. How would one automate the process of creating a schedule for a league such as the NFL?
Even if we ignore all the challenges of a ...
1
vote
1answer
160 views
Complexity of recursive calls
my brain is a little stuck as I am trying to compile an example for my blog. I am presenting an algorithm that draws a number from an array, adds it to a sum and calls itself recursively.
func solve(...
1
vote
2answers
57 views
Modulo complexity within nested loop
i have following code:
for ( int i = 1; i < n; i ++)
for ( int j = 0; j < n*n; j ++)
if (j % i == 0)
for (int k = 0; k < j; k++)
sum++;
How would if (...
1
vote
1answer
179 views
How to solve O (N log N) and more
I got following exercise:
An algorithm takes 0.5 ms for input size 100. How large a problem can be solved in 1 min if the running time is the following:
linear
O (N log N)
...
...
0
votes
1answer
49 views
python snippet optimization explanation
I'm attempting optimize and figure out why for input n a function I wrote f(n) appears to never finish executing when n > 26.
TL;DR
I need to figure out how to find the complexity of various python ...
5
votes
1answer
66 views
Prove complexity for a generic algorithm
I'm new to theory of complexity and am trying to prove a fact.
So, let's consider an algorithm T that receive at input an integer n.
That algorithm has a time complexity for n = 1 : θ(1) and for n > ...
-1
votes
2answers
147 views
Most efficient way to find top values
Let's say we're given n positive integers in random order. What's the most efficient way to find the m largest elements and what's the complexity?
For example, given 1000 values, find the top 10.
-2
votes
1answer
116 views
Considerations when making data structure and algorithm choices [closed]
What are some reasons you may choose a worse runtime algorithm? And what are some advantages of a linked list vs a hash table/array where access is constant time.
5
votes
1answer
154 views
Is it possible to have these characteristics in a data structure?
I was tutoring a student that came up with this assignment. It basically requires a data structure with the following characteristics:
it holds a set of integers in {1, 2, ..., n}
n is power of 2
O(...
5
votes
3answers
319 views
Trying to understand P vs NP vs NP Complete vs NP Hard
I am trying to understand these classifications and why they exist. Is my understanding right? If not, what?
P is polynomial complexity, or O(nk) for some non-negative real number k, such as O(1), O(...
1
vote
3answers
142 views
Is increasing codebase size and complexity worth it to make fully configurable?
I'm re-creating a web app (Google Apps Script) that i made a couple months ago, and decided that I wanted to make it fully configurable this time around. So that I don't have to go in any change any ...
6
votes
2answers
207 views
Does Time Complexity analysis factor for cache performance of an algorithm?
If I have an algorithm A. and it has fewer instructions than algorithm B. but performs worse on a CPU due to poor memory coalescing (and hence, poor CPU cache performance), does that factor into the ...
1
vote
1answer
44 views
Efficiently determining many-to-many subset relation
I'm doing market basket analysis. I have a set of transactions. Every transaction is a set of items that were bought. I then have a set of itemsets (i.e. a set of items) that I want to determine the ...
8
votes
1answer
1k views
Refactoring byzantine payment processing code on a limited budget [closed]
I've been working on a large Ruby on Rails application for several years. It was inherited in a poor state but most of the production bugs have been ironed out with time. There are some sections that ...
1
vote
2answers
319 views
How to write highly changeable, highly complex software? [closed]
I know questions like this has been asked before. But none of them truly answered me.
How to keep a big and complex software product maintainable over the years?
How do you organize highly customized ...
3
votes
1answer
217 views
Burrows-Wheeler transform backward search: how to find suffix index?
BWT backward search algorithm is pretty straightforward if we only need the multiplicity of a pattern. However I also need to find the suffix indices (i.e. positions in the reference string where a ...
-3
votes
1answer
84 views
complexity of an algorithm, sorting 5% out [duplicate]
I have been asked the following question..
An algorithm considers n elements, sorts 5% of n out, considers the remain elements(95%), sorts 5% of the remain elements, and so on until finally one last ...
1
vote
1answer
334 views
How to document GUI screens transitions of a complex application
There is an application based on multiple screen model with pretty complex net of transitions between these screens.
It has some similarities to a web page or Football Manager like games. Its main ...
2
votes
1answer
169 views
Time Complexity when Loop Variable Depends upon Outer Loop Variable
What is the time complexity of the following piece of code in worst case?
s = 0;
for( i = 1; i <= n; ++i ) {
for( j = 1; j <= i * i; j++ ) {
for( k = 1; k <= j and j % i == 0; k++...
1
vote
3answers
328 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 ...
4
votes
2answers
120 views
Check in which region is a geoposition Marker located in
I use Mapbox to display some moving markers over a map with several polygons drew over it (feature layers).
I have serveral markers (~1000) and multiple feature layers (polygons ~200) that represent ...
1
vote
1answer
142 views
How an add vertex operation could be performed in constant time for a graph represented using adjacency list?
Adding a vertex in a graph that is represented using an adjacency list takes O(1) time complexity according to http://bigocheatsheet.com/ (graph operation > adjacency list > add vertex).
It is said ...
4
votes
1answer
436 views
why adding a vertex in a graph represented using an adjacency matrix takes O(|v|^2) time complexity?
Adding a vertex in a graph that is represented using an adjacency matrix takes O(|v|^2) time complexity according to http://bigocheatsheet.com/ (graph operation > adjacency matrix > add vertex).
But ...
9
votes
4answers
855 views
Reducing the complexity of a class
I have looked at some answers and searched on Google, but I could not find anything helpful (i.e., that wouldn't have awkward side effects).
My problem, in abstract, is that I have an object and need ...
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 ...
2
votes
1answer
103 views
Time complexity of update and lookup in binary random access list
I'm trying to get through one of the exercises in Okasaki's "Purely Functional Data Structures," where he presents a zeroless binary numbers as a structure for random-access list, and asks to
9.6 ...
6
votes
3answers
266 views
Why don't “multi-infinite” list comprehensions work with lazy evaluation?
As a simple demonstration of the efficiency of Haskell style, I thoughtlessly ran the following:
take 100 [(a, b, c) | a <- [1..], b <- [1..], c <- [1..], a^2 + b^2 == c^2]
This should be a ...
-6
votes
3answers
750 views
How can the containsKey() method of a Java Hash Table be O(1)? [duplicate]
I had a very large ArrayList in Java, and I often need to check if it contains a particular value. This has proven very slow.
Then I discovered that you can use a data structure based on a Hash. ...
3
votes
1answer
205 views
What is the time complexity of this program?
An algorithm is given on GeeksForGeeks.com for constructing a Binary Search Tree from its preorder traversal.
They say that the time complexity for the following code is O(n^2). But in my opinion it ...
2
votes
1answer
84 views
Seeds distribution algorithm with complexity better than O(n^3)?
I have included my approach and solution. My solution works fine, however, is unoptimized with O(n^3) complexity
An NGO is running seed distribution program. It has limited quantity of varied quality ...
0
votes
2answers
671 views
Efficiently find whether Binary Search Tree is Height Balanced or not?
A binary tree is height balanced if and only if the two subtrees of root are height balanced and the difference between the two subtrees height is at most 1.
I implemented a code in java to find ...
15
votes
4answers
1k views
Are Constant Time and Amortized Constant Time effectively considered equivalent?
I need to write a RandomQueue that allows for appends and random removal in Constant Time ( O(1) ).
My first thought was to back it with some kind of Array (I chose an ArrayList), since arrays have ...
2
votes
1answer
534 views
What are the time and space complexities of this recursive method that reverses a singly linked list?
What are the Time and Space complexities of this Java method that reverses a singly linked list (of length n)?
I'm more interested in knowing the reasoning behind the space complexity. Let me know if ...
