FAQ: Asymptotic Notation: Python - Analyzing Runtime

[wiki-bot]

This community-built FAQ covers the “Analyzing Runtime” exercise from the lesson “Asymptotic Notation: Python”.

Paths and Courses
This exercise can be found in the following Codecademy content:

FAQs on the exercise Analyzing Runtime

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply () below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply () below!

Agree with a comment or answer? Like () to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

[saturnbarz]

Hey, I dont understand how it was figured out that the runtime is O(logn) there was no explanation, hope someone can help!

Thanks

[mtrtmk]

Notice the pattern of how many iterations are being performed when N is being varied to different values.

[saturnbarz]

thats great! thanks, can i ask, where did you get the example you used from, do they have all of the N forms written like this?

[mtrtmk]

If we vary N to the values 1, 2, 4, 8, 16, 32, 64, 128, ... , then you will notice that the count function in your screenshot performs 0, 1, 2, 3, 4, 5, 6, 7, ... iterations respectively.

If you are familiar with the base-2 powers, then the pairing of the two sequences should clue you in that you are seeing a logarithmic relationship between the two sequences.

As an aside, suppose you wrote a different program and varied N to the values 1, 2, 3, 4, 5 ... and noticed that the iterations were increasing in the pattern 1, 4, 9, 16, 25, ..., then the relationship between the two sequences would be quadratic (polynomial) i.e. N²

Coming back to logarithms, for every logarithmic notation, there is an equivalent exponential notation.

For Example, the notation

In base-2, for every increase in the power/exponent, the output is doubled.

So, if you have the sequence 0, 1, 2, 3, 4, 5, 6, ... and the output is 1, 2, 4, 8, 16, 32, 64, ... , then the two sequences have an exponential relationship in the form 2ⁿ
Conversely, if you had the sequence 1, 2, 4, 8, 16, 32, 64, ... and the output was 0, 1, 2, 3, 4, 5, 6, ..., then the two sequences would have a logarithmic relationship in the form log₂(n)

If you had the sequence 0, 1, 2, 3, 4, 5, 6, ... and the output was 1, 10, 100, 1000, 10000, 100000, 1000000, ... , then the two sequences have an exponential relationship in the form 10ⁿ
(In base-10, every increase in the exponent corresponds to a ten-fold increase in the output).
Conversely, if you had the sequence 1, 10, 100, 1000, 10000, 100000, 1000000, ... and the output was 0, 1, 2, 3, 4, 5, 6, ..., then the two sequences would have a logarithmic relationship in the form log₁₀(n)

Perhaps a quick refresher from Khan Academy or some other resource on logarithms and exponents may be useful. Once the logarithm notation is demystified, then it just becomes an exercise in comparing two sequences and classifying whether the two sequences are related in linear or quadratic or exponential or logarithmic or factorial or some other relationship.

[saturnbarz]

Thanks very much!! this was really helpful