The complexity tag has no wiki summary.
2
votes
1answer
428 views
What is the Big-O time complexity of this algorithm [closed]
I was wondering what the run time of this small program would be?
#include <stdio.h>
int main(int argc, char* argv[]) {
int i;
int j;
int inputSize;
int sum = 0;
if(argc == 1)
inputSize ...
2
votes
1answer
680 views
What does it mean when we say that some function is polynomially bigger/smaller than some other function?
I was going over this video lecture on master theorem from Introduction to Algorithm and while explaining case A of the master theorem professor says that some function f(n) is polynomially smaller ...
2
votes
1answer
905 views
How costly are the Python dict and set in-built types?
I have undertaken a project concerning database deduplication. I did some research and have found that the Python dict type actually is a hashmap that uses open addressing.
In the deduplication ...
2
votes
4answers
474 views
Difference between complexity and performance guarantee
I'm a bit confused with the performance guarantee and complexity of selection sort.
I checked through internet and the complexity of selection sort is O(n^2). This O(n^2) is in terms of time ...
2
votes
2answers
805 views
Best resources to really understand run-time complexity
I'm familiar with the basics of run-time analysis such as what makes certain types of code O(n) and O(n^2). But I'm having real trouble learning, understanding, and really remembering how to analyze ...
2
votes
1answer
440 views
Best Upper Bound & Best Lower Bound of an Algorithm
I am studying for a final exam and I came past a question I had on an earlier test.
The questions asks us to find the minimum value in an unsorted array of integers. We must provide the best upper ...
2
votes
2answers
356 views
How do we know if a problem is hardest in NP
I read that the definition of
NP-complete is :
These are the hardest problems in NP. Such a problem is NP-hard and in NP
How do we know if a problem is hardest in NP, and no harder problem ...
1
vote
10answers
1k views
Is it possible to reach absolute zero bug state for large scale software? [closed]
I am talking about 20-30+ millions lines of code, software at the scale and complexity of Autodesk Maya for example.
If you freeze the development as long as it needs to be, can you actually fix all ...
1
vote
3answers
1k views
Big O(n log n) and Quicksort number of operations
I have an Array with 1,000,000 unsorted elements. I need to calculate expected number of operations that needs to be performed to sort array using Quicksort algorithm in common situations (not the n^2 ...
1
vote
1answer
198 views
What is the time complexity of the algorithm to check if a number is prime?
What is the time complexity of the algorithm to check if a number is prime?
This is the algorithm :
bool isPrime(int number){
if(number < 2) return false;
if(number == 2) return true;
if(number ...
1
vote
6answers
3k views
Merge sort versus quick sort performance
I have implemented merge sort and quick sort using C (GCC 4.4.3 on Ubuntu 10.04 running on a 4 GB RAM laptop with an Intel DUO CPU at 2GHz) and I wanted to compare the performance of the two ...
1
vote
1answer
102 views
Algorith analysis refresher help
I haven't touched algorithm complexity stuff in quite a while, so I am trying to do a refresher.
I am trying to figure out the number of steps in the following for loop.
for(i = 0; i < n; ...
1
vote
2answers
149 views
Would a computer engineering degree involve complex event processing?
I've recently discovered the awesomeness of Complex event processing. Just reading the wikipedia page gave me chills on how this technology could be used and evolved into something very powerful.
I'm ...
1
vote
2answers
202 views
complexity of suffix tree question [closed]
Build a suffix tree from a string.
While creating the suffix tree, count re-occurrences of every substring and save it on the number of occurrences on the node.
Then do a BFS search on the tree (from ...
0
votes
1answer
156 views
What can Go chan do that a list cannot?
I want to know in which situation Go chan makes code much simpler than using list or queue or array that is usually available in all languages.
As it was stated by Rob Pike in one of his speeches ...
0
votes
2answers
184 views
Why the bound of a linear function is same as that of a quadratic equation
I am learning algorithms, and I came across something very interesting.
The asymptotic bound of the linear equation (a * n)+b is O(n^2), for all a > 0.
This is same bound as a * n^2 + b * n + c, ...
0
votes
1answer
129 views
Whole Solution Complexity … vs Development Complexity
I am generally a PHP Developer that deals in a few different MVC frameworks. I am being tempted (like most) to break out of my comfortable LAMP environment in pursuit of a "prettier" and "more ...
-1
votes
0answers
90 views
Time complexity (in big-O notation) of the following recursive code? [closed]
public static int abc(int n) {
if (n <= 2) return n;
int sum = 0;
for (int j=1; j<n; j *= 2)
sum += j;
for (int k=n; k>1; k /= 2)
sum += k;
return abc(n ...
-2
votes
1answer
106 views
Algorithm Correctness and Complexity Analysis [closed]
If given an algorithm to traverse a graph (say with a breadth first traversal algorithm). And say you code it in the same manner described in this video tutorial shows (starting at 04:30 for breadth ...
-5
votes
2answers
72 views
Client-side technology stack optimized for durability [closed]
So what's a developer to do when he wants to start a complex long-term project (say 30 years) which is mostly client-side GUI with some logic thrown in and doesn't want to rewrite it every year or ...
