# Tag Info

## New answers tagged runtime-analysis

1 vote
Accepted

### Smallest parameter set for big-O expression

Here is a simple method to find the parameters that can be fixed so that (the problem whose worst runtime is bounded by) a big $O$-expression becomes "tractable", i.e., bounded by some ...
• 32.9k

• 835
Accepted

### Difference between an exact and Big O Notation for worst case runtime

Consider the bubble sort algorithm shown below: ...
• 1,005

### Difference between an exact and Big O Notation for worst case runtime

If nothing precise was specified, you can enumerate all operations by type, such as addition, comparison, swap... and give a detailed account of their numbers. That assumes the the basic operations ...
• 3,231

### Difference between an exact and Big O Notation for worst case runtime

You can’t calculate any runtime except for some very simple model of a CPU. You can calculate the exact number of comparisons, or the exact number of operations moving array elements of a particular ...
• 24.9k
### Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?
In the recursion tree, the cost of the top level (i.e. level 0) is $n^2$. There are two nodes in level $1$, each having a cost of $(n/2)^2$; hence, the total cost of level $1$ is $n^2/2$. In level $2$...
### Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?
Assume $n=16$. Standard MergeSort involves the cost $16+2\cdot8+4\cdot4+8\cdot2$. If we divide by $n$, $1+1+1+1$. "Quadratic" MergeSort involves $256+2\cdot64+4\cdot16+8\cdot4$. If we divide ...