3
$\begingroup$

I'm now doing exam revision, and from some past year exam papers, I noticed some questions that ask to write a recursive method with signature like

public void run(int n)

that must have a time complexity of like : $O(n^2), O(n^3), O(n^7), O(n^2!), O(2^n), O(9^n)$.

Can anyone give some idea on how to solve this kind of recursion questions.

$\endgroup$
  • 4
    $\begingroup$ Are you sure the question doesn't ask for running times of $\Omega(n^2)$, $\Omega(n^3)$, etc? Otherwise the answer is trivial, since the running time of a noop is in the order of any of these classes. $\endgroup$ – Peter Aug 23 '12 at 7:19
  • $\begingroup$ What have you tried? really you couldn't solve any of them? and really you don't have any idea about any of them, show us your try, then we could help you. $\endgroup$ – user742 Aug 23 '12 at 11:00
  • $\begingroup$ @SaeedAmiri from the fibonacci recursion, I was able to write a function with O(x^n) time complexity.But I have no idea how to write a recursive function with time complexity of like O(n^x),O(n2!) $\endgroup$ – Timeless Aug 23 '12 at 14:38
  • 5
    $\begingroup$ Are you sure the exercise asked for $O(…)$ and not $\Theta(…)$? Recommended reading: How does one know which notation of time complexity analysis to use? $\endgroup$ – Gilles Aug 23 '12 at 17:30
  • $\begingroup$ @null, I think you looking for $\Theta$ as Gilles said, your current question is so simple (and I'm wonder why others upvote it), also even you change it to $\Theta$, it's better to clarify your question (I think you mean different recursive methods not unique). $\endgroup$ – user742 Aug 23 '12 at 19:02
7
$\begingroup$

I will assume the person stating the problem actually meant $\Theta$ where you write $O$; otherwise the question is trivial as Juho points out. Realising this may very well have been the point of the problem (or an intended shortcut for the observant), though.

Here is one basic idea to create an algorithm with runtime $\Theta(f(n))$: find a set of objects $S$ with $|S| = \Theta(f(n))$ and recursively enumerate it. If done correctly, this gives you a runtime in $\Omega(f(n))$; if you don't waste time, you get $\Theta(f(n))$.

Some hints for the concrete runtimes you want to achieve:

  • Given a set $T$ of $n$ objects, $|T \times T| \in \Theta(n^2)$.
  • Given a set $T$ of $n$ (distinguishable) objects, the set $\operatorname{Perm}(T)$ of all permutations of these objects has size $n!$.
  • The set $\{0,1\}^n$ contains $2^n$ words.

Note that all these (simple) facts should be known from basic algorithm analysis and formal languages (and maybe combinatorics). The exam question can be solved by generalising and combining them.

$\endgroup$
2
$\begingroup$

The idea is quite simple. Write your function run and analyze its time complexity $r(n)$. Is it then so that you can find any nonnegative constant $c$ and input size $n_0$ such that from which $r(n_0) \leq cg(n_0)$, where $g(n)$ is any particular function you desire? This idea comes from the formal definition of Big Oh. It might be helpful to build up intuition by plotting something, see here.

Here's a concrete implementation. It's not very meaningful, but it doesn't have to be.

void run(int n)
{
  if(n == 0) return;
  run(0);
}

The function is recursive and clearly runs in constant time. It is easy to verify by for example plotting, that yes, at some point $n^2$ and $n^3$ start to dominate. Hence, the the time complexity of the implementation is in both $O(n^2)$ and $O(n^3)$. Similar reasoning holds for other functions.

$\endgroup$
  • 1
    $\begingroup$ -1 Seems you misread the question, OP asked for recursive functions with given time complexity, your answer is just general description of big oh. $\endgroup$ – user742 Aug 23 '12 at 10:52
  • $\begingroup$ @SaeedAmiri Why do you think it's relevant whether the function is recursive or not? This could have easily been a exam question testing your understanding of the big Oh notation. Really, if you know what the notation means the answer is easy and obvious (or the question is misinterpreted as suggested by Peter in the comments). $\endgroup$ – Juho Aug 23 '12 at 11:03
  • $\begingroup$ Thank you very much for reminding me to understand what does big oh mean, I'll take your great advice. But I never said answer is hard (which is obvious from my comment for OP), I said your answer is not an answer to the question, and by your great comment, still I can't see any direct link between your answer and OPs question. $\endgroup$ – user742 Aug 23 '12 at 11:58
  • 1
    $\begingroup$ @SaeedAmiri Being precise and careful is not exaggerating. What is simple and clear to you, might not be that for someone else. It's only my loss if I waste my time answering the question and later on the OP clarifies and the meaning of the question changes. Please don't worry about that. $\endgroup$ – Juho Aug 23 '12 at 18:06
  • 1
    $\begingroup$ @SaeedAmiri: Every function is recursive, even if only trivially so. Look at my set of recursive giraffes: $\varnothing$. $\endgroup$ – JeffE Aug 26 '12 at 1:43
-3
$\begingroup$

When you are given a problem statement there will be an input.The given input has to be countable in some way. In order to get the answer or output you got to manipulate the input in some way are the other in programming. The question is ,how many operation are you going to do on your inputs ... it depends on problem requirement .

For example : In an sorted array of n elements .
      1)searching can be done by checking each and every element . 
      2)And using the mathematical property that array is sorted you apply a very old trick          
       called  binary search .which divedes our search space into half every time we check   
       our trick. This reduces our search space so as reducing the operations.

please read Master theorem to know how to evaluate complexity.

In the case 1 we have complexity in big oh notation as O(n) where n is the input .
In the case 2 we have complexity in big oh notation as O(log(n)) where n is the input .

For basic please refer Big Oh

Coming to the recursion , Suppose our problem be searching, let us consider the binary search .

int binary_search(int A[], int key, int imin, int imax)
{
  // test if array is empty
  if (imax < imin):
    // set is empty, so return value showing not found
    return KEY_NOT_FOUND;
  else
    {
      // calculate midpoint to cut set in half
      int imid = midpoint(imin, imax);

      // three-way comparison
      if (A[imid] > key)
        // key is in lower subset
        return binary_search(A, key, imin, imid-1);
      else if (A[imid] < key)
        // key is in upper subset
        return binary_search(A, key, imid+1, imax);
      else
        // key has been found
        return imid;
    }
}

Firstly for searching an element say X in our input length N then we check middle element in an sorted array to see whether element to be searched(x) is greater or lesser .If it is greater we search the element from middle element(n/2) to last element N recursively .If element to be search(x) is smaller than middle we search from 1 to (n/2) ,as we know that element after middle element is bigger than middle(x

$\endgroup$
  • 1
    $\begingroup$ I downvoted for I don't the relevance of talking about how binary search works when the question is about writing that a function whose time complexity is $f(n)$. $\endgroup$ – Juho Aug 23 '12 at 10:14
  • $\begingroup$ @Juho : after edit I have given the relation . Using recursion for binary search and how complexity changed with each recursion ,as asked in the question . $\endgroup$ – Imposter Aug 23 '12 at 10:19
  • $\begingroup$ Sorry, no. How is knowing how binary search looks like going to help the OP to write a function that runs in $O(9^n)$ time? The details of binary search are totally irrelevant. Thus I don't find your answer useful. $\endgroup$ – Juho Aug 23 '12 at 10:46
  • 1
    $\begingroup$ @Juho: I was trying to explain how complexity is calculated during recursion . OP has asked for general sense .it does mean that we have to show it for each and every O(n2),O(n3),O(n7),O(n2!),O(2n),O(9n). in question $\endgroup$ – Imposter Aug 23 '12 at 11:05
  • 1
    $\begingroup$ I find it totally irrelevant. Perhaps other people disagree with me and upvote your answer. Let's not continue this further. $\endgroup$ – Juho Aug 23 '12 at 11:06

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.