-1
$\begingroup$

I wanted to know something about selection and Time complexity,

for example if I had the f.f.g java code:

public List<String> sort(int n, List<String> ob){
 if(n == 1){
    return binarySort(ob)
 else{
    return selectionSort(ob)
}

I know this is a weird example but I feel it should help me understand what to do when you have selection at the extreme.

How does one go about finding the big oh of the algorithm above? Please note you don't have to go into detail of explaining how big oh found for binary and selection sort.

$\endgroup$
  • $\begingroup$ Worst case performance complexity will be considered as the complexity of this algorithm unless you can prove that the decision factor makes it any better .In the above case selection sort's complexity will be considered the complexity of the overall algorithm. $\endgroup$ – Romantic Electron Aug 13 '17 at 17:11
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Aug 13 '17 at 18:19
  • $\begingroup$ Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael Aug 13 '17 at 18:19
  • $\begingroup$ Mh, what is $n$ ? $\endgroup$ – Yves Daoust Aug 13 '17 at 19:35
2
$\begingroup$

The complexity is defined for $n$ growing to infinity, and the behavior for small $n$ does not matter. (Just like the limit of a sequence does not depend on the first terms).

So the complexity of your snippet is that of selectionSort(ob). And this would still hold with a condition like $n<10^{20}$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

First, note that we measure things in terms of the length of the input, and we traditionally call that quantity $n$. So let's not have an input called $n$. Also, sorting strings is awkward, since you need to take into account the complexity of determining the order of two strings, which can't be done in constant time. So, let's get rid of those issues by rewriting the code as

function sort (int p, int A[])
  if p == 1
      return binarySort (A);
  else
      return selectionSort (A);

Also, note that there's no such thing as "the big-O of an algorithm". Big-O is a notation for comparing the growth rate of mathematical functions: it's a way of writing that one mathematical function (e.g., $f(n)=n$) grows slower than another mathematical function (e.g., $g(n)=4n^2+n\log n$), along with a definition of what "grows slower" means. But it doesn't even make sense to ask "What is the big-O of this mathematical function?" For any function $f$, there are infinitely many functions $g$ such that $f=O(g)$. For example, if $f(n)=3n+6$, all of the following statements are true: $f=O(n)$, $f=O(2n)$, $f=O(n/\pi)$, $f=O(n^6)$, $f=O(2^{4n-6}+\log\log n)$, ... If all of this seems needlessly pedantic, suppose somebody asked you "Hey, what's your less than?" and it turned out they actually wanted your height rounded up to the next centimetre.

So what are you actually looking for? You're probably looking for the asymptotic worst-case running time of your algorithm. Aha, but now the clue is in the name. You just need to consider what is the worst-case running time of the algorithm, for each $n$, and look at how that behaves as $n$ gets large. Well, I don't know what you mean by "binarySort" but the answer is that the worst case for your function sort is whichever is the larger of the asymptotic worst-case running time of binarySort and of selectionSort.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Since there can be a case where almost all of the times n!=1 condition is true $-$ which would be a worst case scenario (considering that Selection sort has a complexity $O(n^2)$ as compared to Binary sort which has complexity $O(n \log n)$). We can generalize the complexity to be $O(n^2)$ for worst case.

If you think that the chance of n!=1 being true has very little probability then in an average case, complexity of your code will be that of Binary sort i.e. $O(n \log n)$

Time complexity is mostly considered for worst case, however there are popular algorithms like quicksort which are preferred because of very less likely-hood of a worst case to happen and their good average case complexity.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.