Linked Questions
10 questions linked to/from Why use comparisons instead of runtime for comparing two algorithms?
1
vote
2
answers
4k
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 ...
- 121
2
votes
2
answers
156
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 ...
- 23
194
votes
3
answers
26k
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 ...
- 72k
25
votes
4
answers
3k
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 ...
- 72k
6
votes
2
answers
16k
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 I ...
- 213
9
votes
2
answers
11k
views
Computational complexity vs Computational cost
Is there a difference between the computational complexity and computational cost of an algorithm?
- 103
8
votes
2
answers
2k
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?
user8722
11
votes
2
answers
486
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, ...
- 245
3
votes
1
answer
637
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,...
- 161
8
votes
1
answer
597
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 ...
