Ch 4. Recursion_Assignment 1

https://colab.research.google.com/drive/1tcVU6aP4jGObq_m6HePgPvtJK3bq29I8#scrollTo=UFvIxDpNhlKm

Approach 1

Using For loop

x^n 계산하기 위해 x를 n번 곱한다. 

def power_with_for_loop(x, n):
    result = 1
    for _ in range(n):
        result *= x
    return result

실행한 결과

Time Complexity Analysis:

• In this approach, we iterate 'n' times, performing a constant-time operation within each iteration.
• Therefore, the time complexity is O(n).

Practical Time Complexity Comparison:

• For n = 100, the algorithm will iterate 100 times, resulting in linear time complexity.

Theoretical Time Complexity Analysis:

• The time complexity is theoretically O(n), as the algorithm iterates 'n' times linearly.

 

---

Approach 2

Using Recursive Algorithm

def power_recursive(x, n):
    if n == 0:
        return 1
    return x * power_recursive(x, n - 1)

실행한 결과

Time Complexity Analysis:

• In this approach, the function calls itself recursively 'n' times.
• Each function call involves a constant-time operation.
• Therefore, the time complexity is O(n).

Practical Time Complexity Comparison:

• For n = 100, the recursive algorithm will make 100 function calls, resulting in linear time complexity.

Theoretical Time Complexity Analysis:

• The time complexity is theoretically O(n), as the function is recursively called 'n' times.

 

conclusion

Both approaches have a time complexity of O(n) theoretically and practically for the given value of n = 100. However, in practice, the recursive approach might suffer from issues such as stack overflow for larger values of n due to the repeated function calls, making the iterative approach more suitable for large inputs. Nonetheless, both algorithms provide linear time complexity for calculating the power of x raised to the nth power.