CS502 is the VU course on design and analysis of algorithms, and Assignment 1 for Fall 2026 focuses on something every algorithms student must learn early: counting how many times each step of an algorithm executes, and then turning those counts into a time complexity. This skill looks mechanical at first, but it is the foundation for comparing algorithms honestly instead of guessing which one is faster.
The solution file linked below works through a factor counting algorithm step by step. It gives the execution count for every step, adds those counts into a total function T(n), and simplifies that total into Big O notation. If you can follow this one example carefully, you can apply the same method to almost any simple algorithm in this course.
What Does the Solution File Cover?
The file covers the complete step count analysis for the factor counting algorithm in Assignment 1. It lists each step of the algorithm, states how many times that step executes in terms of the input size n, and then combines the counts into a single total. The final result is a time complexity of O(n), and the file shows exactly how that result is reached.
What Are the Step Execution Counts?
The analysis assigns one count to each step of the algorithm. The first step executes once, so its count is 1. The loop condition is checked one extra time when the loop finally exits, so its count is n+1. The loop body executes once for each value of the loop variable, so its count is n. The inner test that checks for a factor executes d(n) times, where d(n) stands for the number of divisors involved in the counting process, and the related step also executes d(n) times. The final step executes once, so its count is 1. Written in order, the counts are 1, n+1, n, d(n), d(n), and 1.
How Is the Total Time Complexity Calculated?
The total time function T(n) is the sum of all the step counts. Adding them gives T(n) = 1 + (n+1) + n + d(n) + d(n) + 1, which simplifies to T(n) = 2n + 2d(n) + 3. In Big O analysis, only the fastest growing term matters, and lower order terms and constant factors are dropped. The divisor count d(n) grows much more slowly than n, so the dominant term is n, and the total time complexity is T(n) = O(n). This means the running time grows linearly with the input size, which is the key conclusion of the assignment.
Why Does the Loop Condition Count n+1 Instead of n?
This is the detail students most often miss. A loop that runs n times checks its condition n+1 times, because the final check is the one that fails and ends the loop. Counting only n checks would undercount the work by one. The solution file keeps this distinction visible so your own step counts stay accurate in quizzes and exams.
How Do You Download the Solution File?
You can download the complete solution file from Google Drive using the link below. The file contains the step counts, the total function, and the simplification to O(n).
How Should You Use This Solution?
Work through the counts with a small example before you trust them. Pick a small value of n, trace the algorithm by hand, and check that each step really executes the stated number of times. Fill in your own name and student ID on your submission, and confirm that the steps in your assignment file match the ones analyzed here. Understanding the method matters more than memorizing the final O(n), because exams will ask you to repeat the same counting process on a different algorithm.
- Download the file and read the step count table first.
- Trace the algorithm by hand for a small value of n.
- Check the addition that produces T(n) = 2n + 2d(n) + 3.
- Fill in your own name and student ID on your submission.
- Practice the same counting method on one more algorithm before the exam.
For more study material, you can download course handouts from the VU handouts page and compact revision notes from the VU short notes page. For practice with similar analysis questions, visit the VU final term past papers page.
Frequently Asked Questions
What does d(n) mean in this solution?
In this analysis, d(n) represents the count connected with the divisor testing part of the factor counting algorithm. It appears twice in the step counts because two related steps execute once for each divisor test. Since d(n) grows slowly compared with n, it does not change the final O(n) result.
Why is the answer O(n) and not O(n squared)?
Because no step executes n squared times. The loop body runs n times, and the divisor related steps run d(n) times, which is far smaller than n squared. Adding the counts gives a linear dominant term, so the complexity is O(n).
Can I submit this solution file as it is?
Use it as a study reference. Add your own name and student ID, verify the steps against your own assignment file on VULMS, and make sure you can explain the counting method yourself before submitting.
How can I practice this method further?
Take any simple loop based algorithm, list its steps, count each step in terms of n, add the counts, and drop lower order terms. Past papers contain similar analysis questions, and working through them by hand is the fastest way to build confidence before the exam.
Last updated: October 2026.
