1. Design an algorithm that returns '1' if 'n' is a prime number else returns '0'.
A prime number is only divisible by 1 and itself.
| Parameter \ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Input String | n = 1 or n = 2 | n is a large prime number (e.g., n = 999983) | n = 0 or negative number (n = -7) |
| Output | 0 (for 1), 1 (for 2) | 1 | 0 |
| Explanation | For n = 1, immediately return 0 since 1 is not prime. For n = 2, it’s the smallest prime and directly return 1. | Must check all possible divisors up to √n before confirming n is prime. For large primes, many iterations are required. | Numbers ≤ 1 (including negatives & zero) are not prime by definition, return 0 immediately without iteration. |
2. Design an algorithm that returns the greatest common divisor of the two given positive integers 'm' and 'n'.
| Parameter \ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Input String | (m = 100, n = 0) (One number is zero) | Consecutive Fibonacci numbers e.g., (m = 21, n = 13) | (m = 1, n = 1) (Both numbers are 1) |
| Output | 100 | 1 | 1 |
| Explanation | If one number is zero, GCD is the other number (base case) - algorithm ends immediately. | Fibonacci numbers are known to trigger the maximum number of recursive calls in the Euclidean algorithm, leading to O(log(min(m, n))) complexity. | Minimal inputs where both numbers are the smallest valid positive integers. Edge case often helps validate basic correctness. |
3. Design an algorithm that takes in three integers 'a','b' and 'm' and returns the result of (a^b) % m.
| Parameter \ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Input String | a = 2, b = 0, m = 5 | a = 2, b = 10^18, m = 10^9+7 | a = 0, b = 0, m = 1 |
| Output | 1 (Any number to the power 0 is 1 modulo anything) | Result computed efficiently using fast exponentiation logic | Typically defined as 1 (since 0^0 is mathematically debated) |
| Explanation | - Exponent = 0 ⇒ (a^0) % m = 1 | - Exponent is extremely large. - Requires O(log b) time | - Both base and exponent are 0. - Modulo operation with 1 simplifies to 0 |
4. Design an algorithm that returns all positive divisors of a given integer 'n'.
| Parameter \ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Input String | n = 1 | n = 10^9 | n = prime number (e.g., 13) |
| Output | 1 | List of divisors of 10^9 (many divisors) | 1 and n (since prime numbers have exactly two divisors) |
| Explanation | Only one divisor (1 itself). Loop runs up to √1 = 1 iteration. | Largest possible input, loop runs up to √10⁹ ≈ 31,622 iterations. Returns many divisors. | Prime numbers have exactly two divisors (1 and itself). Loop runs up to √n, but minimal output. |
5. Design an algorithm that takes in a floating-point number 'x' and an integer 'n', and computes x raised to the power n (i.e. compute x ^ n)
| Parameter \ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Input String | x = 1.0, n = any integer | x = non-trivial value (e.g., 2.0), n = very large (e.g., 10^9) | x = 0.0, n = 0 (mathematically undefined but common) |
| Output | Always returns 1.0 (since 1^n = 1) | Large result if n positive, small (fractional) if n negative | Typically handled as 1.0 in programming (0^0 = 1 by convention) |
| Explanation | No matter n, multiplying 1.0 repeatedly always gives 1.0. Very few calculations needed. | Requires multiple recursive/iterative steps (O(log n) complexity), depending on n. | Edge mathematical case (0^0 is undefined); in most systems, treated as 1.0 for simplicity. |