Analysis of Loop in Programming
Data Structures and Algorithm
In this lecture, we will look at some common loops frequently used in
programs and try to find their time complexities. Later, we will examine
functions containing multiple loops and find their time complexities as
well. A ceiling of n by c means that plus or minus some number is a
constant. Therefore, if we find the order of growth, that constant will be
ignored, and the order of growth will be n, resulting in a time complexity
of theta of n. After every pass, we increase i by multiplying it with c until
i becomes more than n. Then we check the condition i < n, which is not
satisfied. We use the condition i < n, which means c raised to the power
k minus 1 is less than something. Now we'll log both sides to base c. If we
find the order of growth of k, we ignore the lower-order term. To find the
time complexity here, we can use mathematics like we did in the
previous example. We need to write i in terms of c. Initially, i is 2, and
then i becomes 2 raised to the power c. C raised to power 0 is 1, and 2
raised to power 1 is also 1, so these two terms are the same. Another
term we can write is 2 raised to power 1 divided by c. 3 is 5 1 2. Three,
which is 5, 1 2 1 1 1. The overall time complexity becomes theta of log
log log n, and the time complexity of our third example becomes theta
log of log n. I hope that you are now able to find the time complexity of
these common loops on your own because these are very common loops.
A nested loop means a loop inside another loop. In this example, we
declared a variable i, which is 0, and after every pass, we increase j by a
constant or multiply it by a constant, which here is 2. In the case of a
nested loop, we multiply the time taken by the first loop into the time
spent by another loop, resulting in this. You can see this logic.
Data Structures and Algorithm
In this lecture, we will look at some common loops frequently used in
programs and try to find their time complexities. Later, we will examine
functions containing multiple loops and find their time complexities as
well. A ceiling of n by c means that plus or minus some number is a
constant. Therefore, if we find the order of growth, that constant will be
ignored, and the order of growth will be n, resulting in a time complexity
of theta of n. After every pass, we increase i by multiplying it with c until
i becomes more than n. Then we check the condition i < n, which is not
satisfied. We use the condition i < n, which means c raised to the power
k minus 1 is less than something. Now we'll log both sides to base c. If we
find the order of growth of k, we ignore the lower-order term. To find the
time complexity here, we can use mathematics like we did in the
previous example. We need to write i in terms of c. Initially, i is 2, and
then i becomes 2 raised to the power c. C raised to power 0 is 1, and 2
raised to power 1 is also 1, so these two terms are the same. Another
term we can write is 2 raised to power 1 divided by c. 3 is 5 1 2. Three,
which is 5, 1 2 1 1 1. The overall time complexity becomes theta of log
log log n, and the time complexity of our third example becomes theta
log of log n. I hope that you are now able to find the time complexity of
these common loops on your own because these are very common loops.
A nested loop means a loop inside another loop. In this example, we
declared a variable i, which is 0, and after every pass, we increase j by a
constant or multiply it by a constant, which here is 2. In the case of a
nested loop, we multiply the time taken by the first loop into the time
spent by another loop, resulting in this. You can see this logic.
