Hi!
i am stuck in figuring out the bog O for such nested loop
for s=1 to s<N
{
for e= 1 to e< min(M,s-1)
{
do some work
}
}
if we assume tht M is very large value (but less than N) then the inner loop runs for
0+1+2+.....M times and outer loop runs for N times
so runs of both will always be less than MN
Is the complexity still O(MN)
or we have a better and more efficient statement for O??
Plz help me out.
Regards
Well, technically, that code is Big-Oh of N^2 since T(N) is certainly bounded by some quadratic.
Of course, if M is less than a linear function of N (i.e. it is constant or polylogarithmic) then the bound will simply be the simplest form of O(MN) upon replacing M with its expression in N. For example,
M = 1,000,000,000,000,000,000,000,000,000,000 = const.
O(MN) = O(1,000,000,000,000,000,000,000,000,000,000 * N) = O(N)
M = log(N)
O(MN) = O(N log N)
If you have no information about how M depends on N, the best you can say is O(MN).
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.