Recurrence relation: T(n) = T(ceil(n/3)) + T(ceil(3n/5)) + 100*n

You can use the Akra-Bazzi theorem.. To do that, you can use this fact that ceil(x) = x + 1 - {x} such that {x} is the fractional part of x.

Therefore, you can rewrite the complexity term such as the following:

T(n) = T(n/3 + 1 - {n/3}) +‌ T(3n/5 + 1 - {3n/5}) + 100n

Hence, the parameters in the theorem are:

a1 = a2 = 1, 
b1=1/3, b2 = 3/5, 
h1(n) = 1 - {n/3}, h2(n) = 1 - {3n/5},
g(n) = 100n

As you can see 0 < b1, b2 < 1, a1, a2 > 0, h1, h2 < 1, and g(n) is linear. It means all requirements of the theorem are holding.

Now, it is time to find p such that:

(1/3)^p + (3/5)^p = 1 => p ~ 0.9

Therefore, T(n) = Theta(n^p (1 + int(100 u/u^{p+1}, 1, n)). To simplify the term, we need to compute the integral:

int(100 u/u^{p+1}, 1, n) = 100 * int(1/u^p, 1, n) = 100 (n^{1-p}/(1-p) - 1)

So the simplified term of the complexity is T(n) = Theta(n).

@OmG's answer using the Akra-Bazzi theorem does a great job showing off how to use that mathematical tool. Here's a different way to see why the runtime is O(n) using a recursion tree.

Let's start off by drawing the top two layers of the recursion tree:

                      +--------------------+
                      | n items, 100n work |
                      +--------------------+
                     /                      \
     +------------------------+    +-------------------------+
     | n/3 items, 100n/3 work |    | 3n/5 items, 300n/5 work |
     +------------------------+    +-------------------------+

Purely for convenience, I'm leaving the ceilings off, since they won't make a difference in the overall analysis.

Notice that the work done at the second layer is equal to

100n / 3 + 300n / 5 = 500n / 15 + 900n / 15 = 1400n / 15 = 100n * (14 / 15),

which is lower than the work done one layer above. Specifically, the work here has decreased geometrically by a factor of 14/15. And indeed, each time we make a recursive call, the two subcalls will collectively do a 14/15 fraction of the work one level above it.

This means that the total work done by all the recursive calls is

(work in layer 0) + (work in layer 1) + (work in layer 2) + ...

≤ 100n + (14/15) · 100n; + (14/15)² · 100n + (14/15)³ · 100n + ...

≤ 100n(1 + (14/15) + (14/15)² + (14/15)³) + (14/15)⁴ + ...)

That last sum is the sum of a geometric series, and it works out to

1 / (1 - 14/15) = 1 / (1/15) = 15,

so the total work done is at most 1500n.

Intuitively, if you see a recursion tree like this where the work done per level drops by a constant from one level to the next, then the total work done will just be some constant multiple of the work done at the top level. The Master Theorem and its generalization the Akra-Bazzi theorem essentially formalize this idea by quantifying the conditions under which this occurs and giving an exact closed-form solution to them. But if you see a recurrence like this one in the future, where the work drops geometrically from level to level, you should have a "gut feeling" that the work done in total will sum to at most some multiple of the top level.

(You can try this out on the famous recurrence for the median-of-medians algorithm T(n) = T(n / 5) + T(7n / 10) + n, in which there's a similar decay from one layer of the tree to the next.)

In doing this analysis, I left out all of the floors and ceilings, which is not mathematically safe to do in all cases. But here, it ends up being okay, since the slight amounts that we're off by at each level don't add up to all that much across the whole tree. To prove this, you could use the substitution method and try proving an exact bound on the work done.