Linked Questions

162
votes
3answers
17k views

Is there a system behind the magic of algorithm analysis?

There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis). Many are similar, for instance those asking for a cost analysis ...
23
votes
4answers
2k views

How to fool the plot inspection heuristic?

Over here, Dave Clarke proposed that in order to compare asymptotic growth you should plot the functions at hand. As a theoretically inclined computer scientist, I call(ed) this vodoo as a plot is ...
10
votes
2answers
239 views

Is there any standard for comparing runtimes experimentally?

My situation I am writing a paper presenting a software module I developed and I want to compare its runtime to other modules for the same task. I am aware of the drawbacks of runtime experiments, ...
8
votes
2answers
844 views

What constitutes one unit of time in runtime analysis?

When calculating runtime dependence on the input, what calculations are considered? For instance, I think I learned that array indexing as well as assignment statements don't get counted, why is that?
8
votes
1answer
120 views

What counts as an operation?

Apologies for the newbie question, but I am a bit confused about what exactly counts as a "simple operation" when working out the time complexity of an algorithm. In particular, why do we consider all ...
4
votes
2answers
9k views

What is the complexity of this matrix transposition?

I'm working on some exercises regarding graph theory and complexity. Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically ...
4
votes
2answers
5k views

Computational complexity vs Computational cost

Is there a difference between the computational complexity and computational cost of an algorithm?
3
votes
1answer
387 views

Compare asymptotic WC runtime with measured AC runtime

I have an algorithm and I determined the asymptotic worst-case runtime, represented by Landau notation. Let's say $T(n) = O(n^2)$; this is measured in number of operations. But this is the worst case,...
2
votes
2answers
111 views

Why comparison is dominant time consumption for comparison-based sorting algorithms? [duplicate]

Comparison-based sorting algorithms does a number of different operations to accomplish the sorting, why comparisons are the dominant time consumption? While I understand the standard analyses of ...
0
votes
2answers
2k views

Why don't we calculate swaps and other steps except comparison for finding time complexity of a sorting algorithm? [duplicate]

I was learning some basic sorting techniques with their complexity. However I cannot understand why only the number of comparisons are taken into account while calculating time complexity and ...