CS502 ASSIGNMENT NO. 1 SPRING 2023 || 100% RIGHT SOLUTION || FUNDAMENTALS OF ALGORITHMS || BY VuTech

Visit Website For More Solutions
www.vutechofficial.blogspot.com

KINDLY, DON’T COPY PASTE

SCENARIO:

Consider a natural number (or integer number) 58473, the digits of this number are 5, 8, 4, 7 and 3. If we need to sum the digits of this number then it is equal to 5 + 8 +4 +7+3 = 27.

There may be many algorithms that can be written to add the digits of an integer numbers.

QUESTION-1:

You are required to design (write) a simple algorithm (Only Pseudo code) that will add (sum) the digits of an integer number.

SOLUTION:

Here's a simple algorithm in pseudo code to sum the digits of an integer number:

1. Initialize a variable "sum" to 0.

2. Convert the given integer number to a string.

3. Iterate through each character in the string:

   - Convert the character back to an integer.

   - Add the integer value to the "sum" variable.

4. Output the final value of the "sum" variable.

QUESTION-2:

You are required to calculate (Step by Step) the worst case time complexity T(n) of the algorithm designed in Question No. 01.

SOLTUION:

To calculate the worst-case time complexity T(n) of the algorithm, let's analyze the steps involved:

Step 1:

Initializing a variable "sum" takes constant time, so it can be considered O(1).

Step 2:

Converting the given integer number to a string requires converting each digit individually. The number of digits in the worst case scenario would be log10(n). So, this step has a time complexity of O(log n).

Step 3:

Iterating through each character in the string requires visiting each digit once. In the worst case scenario, the number of digits would be log10(n). So, this step has a time complexity of O(log n).

Step 3.1:

Converting each character back to an integer takes constant time, so it can be considered O(1).

Step 3.2:

Adding the integer value to the "sum" variable takes constant time, so it can be considered O(1).

Step 4:

Outputting the final value of the "sum" variable takes constant time, so it can be considered O(1).

Considering all the steps, the total worst-case time complexity T(n) of the algorithm is:

T(n) = O(1) + O(log n) + O(log n) + O(1) + O(1) + O(1) = O(log n)

Therefore, the worst-case time complexity of the algorithm is O(log n).

KINDLY, DON’T COPY PASTE
SUBSCRIBE, SHARE, LIKE AND COMMENTS FOR MORE UPDATES
SEND WHATSAPP OR E-MAIL FOR ANY QUERY
0325-6644800
kamranhameedvu@gmail.com
Visit Website For More Solutions
www.vutechofficial.blogspot.com