0

what will be the run time of the following code segment in terms of big O? [assuming f1(n)=O(n)]

function Recurse(A[1..n])
        f1(n)
        t1 <-- Recurse(A[1..(n-1)])
        t2 <-- Recurse(A[(2..n])
        return (t1+t2)
end function

is it O(n) ?? or something else?

CSchulz
  • 10,882
  • 11
  • 60
  • 114
SK50
  • 1
  • 1
    This question appears to be off-topic because it is theoretical not practical. Try http://cs.stackexchange.com – Raymond Chen Sep 21 '14 at 14:36
  • @RaymondChen please highlight some specific text on the SO pages that says a question like this is off topic. – chiastic-security Sep 21 '14 at 14:40
  • @chiastic-security "Questions asking for homework help must include a summary of the work you've done so far to solve the problem, and a description of the difficulty you are having solving it." – David Eisenstat Sep 21 '14 at 15:25
  • @chastic-security Right there on [the tour](http://stackoverflow.com/tour) in big letters. "Get answers to practical, detailed questions." Theoretical questions are not practical. Also number four on the "Do not ask" list: Anything not directly related to writing computer programs – Raymond Chen Sep 21 '14 at 16:31
  • Looks directly related to writing computer programs to me. OP wants to find out algorithm runtime for a fairly specific type of recursion. – Jason S Sep 21 '14 at 17:34
  • @RaymondChen It looks directly related to writing computer programs to me too. And it is immensely practical: knowing the algorithmic complexity of your algorithm tells you whether it'll be fit for purpose in the context in which you're deploying it. Do you think it's a practical issue that quicksort is O(n log n) and bubblesort is O(n^2)? And are you going to try to close [this question](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) too (2367 votes, 2088 faves)? – chiastic-security Sep 21 '14 at 18:30
  • Wiring the code is programming. But this is purely a theoretical level. There is no practical problem being solved. It's an unmotivated exercise. – Raymond Chen Sep 21 '14 at 18:50

1 Answers1

0

This is exponential in invocations of f1: O(2^n) invocations. So if f1 is O(n) then this will come out as O(n 2^n).

You've got n steps, and at each point, it subdivides into two branches. It's the same as a complete binary tree of height n.

chiastic-security
  • 20,430
  • 4
  • 39
  • 67