CODEWITHSUNDEEP
javaalgorithmdata-structurestime-complexitycomplexity-theory
nullr4pt0r
nullr4pt0r

Reputation: 21

Is Outer loop iterations are considered here in the nested loops, where inner loops iterations depends on outer loop values?

Code 1

    for(int i=1-N)
        for(int i=1-M)

The inner loop runs M times each Outer loop iterations.Outer loop N times , Inner loop M times. TC = O(N*M)

Code 2

    for(int i=1-N)
        for(int j=1-i)

The outer loop runs N times. Inner loop iterations are not fixed here. It runs based on the outer loop i value.

Inner loop iterations are 1,2,3,....N. Applying the Sum of N natural numbers formula we get N(N + 1) / 2.

Time Complexity will be O(N^2).

My confusion is , outer loop runs N times. Inner loop runs based on outer loop i value.

will the TC find like this ?

Outer loop + inner loop (sum the loops because the inner loop value based on outer loop values) N + N(N + 1) / 2 = 2N + N^2 =\ neglecting the lower order as per Big Oh principles = O(N^2).

Is my approach correct here ?

As per my understandings,

  1. If inner loop values runs irrespective of outer loop values like code 1, We should multiply the outer loop iterations and inner loop iterations.

  2. If the inner loop runs based on the outer loop values and not fixed number of iterations like code 2, we should sum the outer loop iterations and inner loop iterations.

Also please clarify when to Multiple the nested loop iterations, when to sum the nested loop iterations.

I am just learning the DSA in java. This time complexity finding confusing me.

Upvotes: 0

Views: 63

Answers (1)

Rahul Singh
Rahul Singh

Reputation: 335

Is my approach correct here ?

Yes, it is.

Also please clarify when to Multiple the nested loop iterations, when to sum the nested loop iterations.

Well, it depends on the algorithm you are trying to solve. Try changes you perspective a little bit. See, we are using no. of operation as a proxy for time here, right? So all we need to do is find the total number of unit operation required i.e. sum. So for you code example one, we can say:

T.C = m + m + m + m +....+ m

How many times are we adding the m options ? N times right ? that why, we are writing it as m * n

Practice more. Try to find the T.C's of recursive problems, it will give you more clarity

Upvotes: 0

Related Questions