2022 Developer Survey is open! Take survey.

# Tag Info

Accepted

### A little confusion with Big Theta time complexity

"for some input size $n$ greater than $n'$" is wrong. The correct statement is "for all input sizes $n$ greater than $n'$". Obviously, $$\frac{n^3}2\le n^2\le 2n^3,$$ which is ...
• 3,357

### A little confusion with Big Theta time complexity

If $f(n) \in O(g(n))$ and $g(n) \in O(f(n))$ then $f(n) \in \Theta(g(n))$, otherwise $f(n) \not\in \Theta(g(n))$. $n^2 \in O(n^3)$ but $n^3 \not\in O(n^2)$ so $n^2 \not\in \Theta(n^3)$. It works ...
Accepted

### How to find parameter sets for a big-O expression to be fixed-parameter tractable?

Here is a simple method to find the parameters with respect to which (the problem whose worst runtime is bounded by) a big $O$-expression becomes fixed-parameters tractable (FPT), i.e., bounded by a ...
• 33.1k
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,357

### 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

### Time complexity when taking certain elements and iterating over them?

In doing running-time analysis, we often assume the worst-case. That is, what scenario will lead to the maximum possible running-time. As for your question about the second array, you can assume that ...
• 1,257

### Help with model answer for time complexity

Observe that after index is incremented from n to n+1 by line 6, the condition in line 3 is tested one last time (this condition evaluates to False because index=n+1, which is not <=n) before the ...
• 1,005

### Help with model answer for time complexity

The number of iterations of the body of the loop is $\max(0,n-1)$. The number of comparisons performed at line $3$ is $\max(1,n)$. For both, best case and worst case are identical. If the answer sheet ...
• 3,357