# Tagged Questions

118 views

### problem on calculating Big O complexity

i have this function on which i have to calculate the time complexity with the Big O notation: public void print(ArrayList<String> operations, ArrayList<LinkedHashSet<String>> ...
198 views

### What is a O(n) algorithm to solve this puzzle?

We are going to hold a meeting where everybody will speak in clockwise direction around a table. There are n people with n spots. Each person has a position preference (e.g. some want to go first, ...
299 views

### Binary Search seems superior, why did the committee of C++ still have Find in the algorithm library?

I wish to search for an integer in a vector of integer. I have two candidates for the job: Binary Search Find It seems that Binary Search is the best candidate for the job as although I have to ...
297 views

### difference between exponential and logarithmic growth

Why for(k=1;k<=n;k*=2) grows logarathmically = O(logn) but I feel it grows exponentially, as the seq look like 1,2,4,8.... and for fibonacci series people say it grows exponentially. which for me ...
1k views

### Complexity in nested loops

Foreword: In this post, I will make the common confusion between O(n) and Theta(n) as complexity notations. I will write pseudo-code to talk about algorithms, using whatever notation I find to my ...
76 views

### why the time complexity of Quick sort is better than heap sort and merging sort? [duplicate]

the heap sort\Merging sort\Quick sort all have the same time complexity nlogn. why the quick sort is better than others?
1k 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 ...
222 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, ...
2k views

### What does it mean by expected running time and average runnnig time of an algorithm?

Let's say we want to analyze running time of algorithms. Sometimes we say that we want to find the running time of an algorithm when the input size is n and for the worst possible case it is denote it ...
2k 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 ...
3k 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 ...
2k views

### What would be the Impact of P=NP? [closed]

I am preparing for a test and I can't find a clear answer on the question: What would be the impact of proving that PTIME=NPTIME. I checked wikipedia and it just mentioned that it would have "profound ...
7k 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 ...
11k views

### Determining if an Algorithm is O (log n)

I'm refreshing my CS Theory, and I want to know how to identify that an algorithm O (log n) complexity. Specifically, is there an easy way to identify it? I know with O(n), you usually have a single ...
3k views

### Magic square check for N×N matrix with minimum complexity

Is there any algorithm that works better than O(n²) to verify whether a square matrix is a magic one (e.g. such as sum of all the rows, cols and diagonally are equal to each other)? I did see someone ...
2k views

### Smallest lexicographical rotation of a string using suffix arrays in O(n)

I will quote the problem from ACM 2003: Consider a string of length n (1 <= n <= 100000). Determine its minimum lexicographic rotation. For example, the rotations of the string “alabala” ...
750 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 ...
146 views

### Algorithm 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; ...
1k views

### Why is the formal definition of Big O notation formulated as such?

Consider the formal definition: f(n) = O(g(n)) Why is it not: f(n) = O(f(n)) or f(n) = O(c*f(n)) since for the Big O analysis, f(n)=2n and g(n)=n are identical? I am ...
2k views

### Big-O for nested loop

I am reading this post on Big-O It says that the following code is O(n^2): bool ContainsDuplicates(String[] strings) { for(int i = 0; i < strings.Length; i++) { for(int j = 0; j ...
663 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 ...
247 views

### Complexity vs maintainability in modern hardware

Today with the modern hardware and memory coming cheap, how much sense does it make to spend effort to analyze algoriths or data structure complexity? Wouldn't it be better instead, to focus on clean, ...
2k 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 ...
271 views

### Process each row against each other, how much would it cost?

If I have n rows in a database, and I want to compare every row against each other, how many loops (or processes) would I need to do. Is it n2? (so if I have 30,000 rows then it would be 900,000,000) ...
592 views

### Subset sum problem is NP-complete?

If I know correctly, subset sum problem is NP-complete. Here you have an array of n integers and you are given a target sum t, you have to return the numbers from the array which can sum up to the ...
418 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 ...
241 views

### NP hard/complete

I have never been very clear on this concept. Please help: At the end of the day, we should want to identify useful problems for which we don't have polynomial solution so far and only have ...