Inscrivez-vous ou connectez-vous pour rejoindre votre communauté professionnelle.
We always give priority to time complexity rather than space complexity. if we use a sequence of for loops instead of nested for loops then the time complexity is same.But still why do people insist for a beginner to use nested for loops even though he feels it confusing
Nested for loops are when you have one or more loop inside a loop.
your inner loop does a task, which actually is iterative in nature and your outer loop does that task again and again depending on your condition. We generally use them a lot for printing or getting value for 2d array.
the complexity
It depends on the condition given in the for loop. An algorithm is said to be O(n^2) if for all of n elements, the code is executed n times. If you give a condition in the inner loop that will always terminate the inner loop and/or outer loop without executing n times for all elements, then it will have less than O(n) time complexity.Similarly, the condition you give in the inner loop can make it more than O(n^2). The number of execution steps determine the order of the algorithm.
Let's make things clear in the first.
For loop is used to obtain a variable that iterates on given array of elements
First: when we use a single for loop ??
when you want to form iteration on a 1D array, where you use variable to track the number of the current element
for ex: x = [1,2,3]
so you will iterate with variable (say i) on each element one at a time
then
at i =1: x[i]=1
at i =2: x[i]=2
at i =3: x[i]=3
If you interested in complexity time as you see it depends on the number of elements in array assume it's "n" then the (O) = n (obviously linear)
And of course, if we used series of for loops (not nested), assumes they are "S" loops, it would have big notation O = S*n which is approximately n
Second: When we nested single for loop in another for loop ??
when you want to form iteration on a 2D array, where you use 2 variables to track current element (variable of the outer loop for no. of row and the variable of the inner loop is for the columns)
for ex: x = [[ 1 , 2 , 3],
[ 4 , 5 , 6],
[ 7 , 8 , 9]]
so you will iterate with variable (say i) on each element one at a time at the outer for and another variable (say j) on the inner for loop
then
at i =1 and j = 1: x[i]=1
at i =1 and j= 2: x[i]=2
at i =1 and j =3: x[i]=3
at i =2 and j = 1: x[i]=4
.
.
so on
For complexity time as you see it depends on the number of elements in product of the two arrays (as we execute the inner loop number of times equal the number of elements in the outer array)assume there is "n" elements in outer and "n" in the inner array then the (O) = n^2 (obviously quadratic)
And of course, if we used series of for loops ( each nested with one for loop only), assumes they are "S" loops, it would have big notation O = S*n^2 which is approximately n^2
Third : When to nested a for loop inside another for that nested in another for loop :D ??
when you want to form iteration on a 3D array,where you keep track of element in the current matrix ( outer loop varible for the no. of matrix, middle loop variable for the row and the inner for the column)
for ex: x = [[[1,2,3],[4,5,6],[7,8,9]],[[10,11,12],[13,14,15],[16,17,18]],[[19,20,21],[22,23,24],[25,26,27]]]
so you will iterate with variable (say i) on each element one at a time at the outer for, another variable (say j) on the middle for loop and variable(say k) on the outer for loop
then
at i =1, j = 1,and k =1: x[i]=1
at i =1, j= 2 and k =1: x[i]=4
at i =1, j =1 and k =2: x[i]=2
at i =2,j = 1 and k =1: x[i]=10
.
.
so on
For complexity time as you see it depends on the number of elements in product of the 3 arrays (as we execute the inner loop number of times equal the number of elements in the middle array and we repeat this process number of times equal to the number of elements in the inner)assume there are "n" elements in outer,"n" in the middle and "n" elements in the inner array then the (O) = n^3 (obviously Cubic)
And of course, if we used series of for loops ( each nested with two for loop only), assumes they are "S" loops, it would have big notation O = S*n^3 which is approximately n^3
I hope it's clear now when, why and even How to use nested loops
and if you still have some doubts there is an example I saw on the internet that can illustrate the case more
note Idon't know which programming lang. you use so I will try to use the most common form and I think it's common in c/c++ and Java for(int month=1;month<=12;month++){
//start of a new month for(int day=1;day<=31;day++){ //start of the 31 days of the month Do something } //end of a month } //end if the year }so the inside loop iterates on each day in given month from the outer loop
so we have 12 months and each month have 31 days (consider this fact is true :D)
Finally: for short answer on your question sequence for loops is far better then using nested for in case of time, and when to use a nested loop, just use it when you don't have any alternatives, try not to complicate things the more simple the better.
using loops depends on the problem you may use nested loops to sort a table of numbers (sorting algorithms), generaly the complexity of an algorithm with nested loops > with sequence of loops
when to use its deppend on the program case but the most time when we want to repeat some task in sequnace
for time complexity
one for loop will be O(n) , 2 for loop will be O(n^2) and soo one but if the counter is not increaminted using + or - if we use mul or div the for lop will equal to O(logn) and if the counter deacred exponitialy will be O(loglogn)
well sometimes using nested loops is your only solutuion for example take any complex problem that needs iteratiing over an array and for each value iterate over another array to get the job done like building an array of the amount of numbers from array A2 that are less or equal to each value in array one if u can do this in sequence of loops then you are a genuis 'dont just repeat it fixed number of times your algotithm should work with all sizes'
for loops is one of the codes that have a powerful benefit. we use it to break down the problem into smaller chunks and solve them separately. Of course, it is inner for loop within the body of an outer one.
nested for loop is used when we are trying to iterate multiple arrays which are dependent on each other.
nested loop took more time to execute than loops in sequence.