Scribd
Upload
7 views

Algorithms Assignment (2)

Uploaded by

mostafaabdelatif24
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
7 views

Algorithms Assignment (2)

Uploaded by

mostafaabdelatif24
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Mostafa Mahmoud

C2200881
Assignment (2)
Q1:
1. Design a sequential algorithm for a selected
computational chosen problem, then analyze it
according to:
a) complexity, b) simplicity , c) correctness.

SOLVE:

Problem: Sorting an array of

numbers. Algorithm: Bubble Sort

1. Start from the first element and compare it with the next one.
2. If it is larger, swap them.
3. Repeat for all elements in the array.
4. Repeat steps until no more swaps are needed.

Analysis:

 Complexity:
o Worst-case time complexity: O(n2)O(n^2)O(n2)
o Best-case time complexity (already sorted): O(n)O(n)O(n)
 Simplicity:
Easy to understand and implement but inefficient for large datasets.
 Correctness:
The algorithm guarantees the array is sorted after all passes.

2. List a pseudocode for a recursive algorithm and


compute its time complexity

SOLVE:

Problem: Calculating the factorial of a number

nnn. Pseudocode:

function factorial(n):
if n == 0:

return 1

else:

return n * factorial(n - 1)

Time Complexity:

 Each recursive call decreases nnn by 1 until n=0n = 0n=0, leading to O(n)O(n)O(n)
time complexity.

You might also like