1

I understand the concept of the Big O notation and its something i've brought upon myself to learn recently.

But say for a given algorithm, which recursively calls itself until the job is complete, if there is an OR in my return statement, how will that effect the Big O notation?

Here's the algorithm thus far:

**Algorithm: orderedSort(a,b,c)**
given strings a,b,c determine whether c is an ordered shuffle of a and b

l := length of (a + b)
if (l = 0) then
    return true
if (l not = length of c)
    return false
else
    d := substring of a position 1 to 1
    e := substring of b position 1 to 1
    f := substring of c position 1 to 1
if (d = f) then 
    return orderedSort(a-d, b, c-f) 
if (e = f) then
    return orderedSort(a, b-e, c-f)
if (d and e = f) then
    return orderedSort(a-d, b, c-f) or orderedSort(a, b-e, c-f)

Does having the or make it n^2?

Improve this question
6
  • You need to identify the worst possible sequence of recursive calls that the function can generate. i.e. find the worst possible inputs for a,b,c which will yield the most calls. Commented Nov 15, 2015 at 16:29
  • And how do I do that @oarfish Commented Nov 15, 2015 at 16:38
  • Looks like there is something missing in your algorithm? Commented Nov 15, 2015 at 16:55
  • whats that? @gnasher729 Commented Nov 15, 2015 at 16:58
  • 1. If d = f or e = f then the third if is never reached. 2. After the third if, there is no return statement. Further, if l = 0 then "true" is most likely the wrong answer, say a = "x", b = "y", c = "xyz". Commented Nov 15, 2015 at 17:13

1 Answer 1

Reset to default
1

It's far worse than you think. If both halves of the "or" will need to be evaluated some % of the time, then you will end up with O(2^n) (not O(n^2)) recursive calls.

Let's say it takes both halves of the OR 10% of the time. On average you have to go down 10ish levels before you do both halves, so you have around:

1 call with length n
2 calls with length n-10
4 calls with length n-20
8 calls with length n-30
...
2^(n/10) calls with length 0

Also, it's worse than that again, because all those string manipulations (length(a+b), a-d, etc.) take O(n) time, not constant time.

EDIT: I should mention that O(2^n) is not actually correct. It's "exponential time", but O(2^(n/10)) or whatever is strictly less than O(2^n). A correct way to write it is 2^O(n)

EDIT:

A good solution for this problem would use dynamic programming.

Let OK(i,j) = true if the first i+j characters of c are an ordered shuffle of the first i characters of a and the first j characters of b.

OK(i,0) is easy to calculate for all i. Then you can calculate all the OK(i,j) from OK(i,j-1). When you've covered all the cases with i+j = length(c), then return true if any one of them is true.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.