Summary Analyzing Time Complexity of Loops in Programming: Understanding Common Loop Structures and Nested Loops
3 views 0 purchase
Course
Data Science MS
Institution
Data Science MS
This document provides an in-depth understanding of time complexity and how it relates to loops in programming. The document explores common loops used in programs and provides examples of how to calculate their time complexity. It also covers nested loops and how to calculate their time complexity...
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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller user111. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $10.49. You're not tied to anything after your purchase.
