2022 Developer Survey is open! Take survey.

New answers tagged

0 votes
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 ...
user avatar
  • 3,357
2 votes

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 ...
user avatar
3 votes
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 ...
user avatar
  • 33.1k
0 votes
Accepted

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

Consider the bubble sort algorithm shown below: ...
user avatar
0 votes

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 ...
user avatar
  • 3,357
2 votes

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 ...
user avatar
  • 24.9k
2 votes

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 ...
user avatar
  • 1,257
0 votes

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 ...
user avatar
0 votes

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 ...
user avatar
  • 3,357
0 votes

What is the BigO of a C# function when runtime is 3n - logn + 1

A general rule of thumb when expressing a function in big O notation is to discard the lower order terms, and to discard the coefficient in the dominant term. For large n, 3n dominates 3n-log n +1, ...
user avatar
-3 votes

What is the BigO of a C# function when runtime is 3n - logn + 1

I'm not 100% sure but I think it is O(n2)
user avatar

Top 50 recent answers are included