5
votes
1answer
536 views

How can I compute the Big-O notation for a given piece of code? [closed]

So I just took a data structure midterm today and I was asked to determine the run time, in Big O notation, of the following nested loop: for (int i = 0; i < n-1; i++) { for(int j = 0; j < ...
8
votes
2answers
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 ...
1
vote
6answers
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 ...
3
votes
1answer
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 ...
5
votes
4answers
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 ...
2
votes
6answers
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, ...
2
votes
2answers
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 ...
8
votes
5answers
572 views

How much redundancy/robustness should complex software implement?

The focus of this question: Some software performs "extra work" in order to increase the chance of a "eventually successful/satisfactory" outcome, despite one or more internal errors in the software, ...