Time and space complexity of an algorithm and Purpose

2 posts Tue, Apr 20, 2021 at 09:06 AM in General Algorithm Discussions

Hi Experts,
I have confussion of the following algorithm in terms of time and space complexity and purpse. Could you find the above mentioned terms of the following algorithm.

Mystic Algorithm
𝑝𝑟𝑜𝑐𝑒𝑑𝑢𝑟𝑒𝑀𝑦𝑠𝑡𝑒𝑟𝑦𝐴𝑙𝑔(𝑥,𝑛)
𝑖𝑓 𝑛=0 𝑡ℎ𝑒𝑛
𝑟𝑒𝑡𝑢𝑟𝑛 1
𝑒𝑛𝑑 𝑖𝑓
𝑖𝑓 𝑛=1 𝑡ℎ𝑒𝑛
𝑟𝑒𝑡𝑢𝑟𝑛 𝑥
𝑒𝑛𝑑 𝑖𝑓
𝑖𝑓 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛 𝑡ℎ𝑒𝑛
𝑟𝑒𝑡𝑢𝑟𝑛𝑀𝑦𝑠𝑡𝑒𝑟𝑦𝐴𝑙𝑔(𝑥∗𝑥,𝑛2)
𝑒𝑙𝑠𝑒
𝑟𝑒𝑡𝑢𝑟𝑛 𝑀𝑦𝑠𝑡𝑒𝑟𝑦𝐴𝑙𝑔(𝑥∗𝑥,𝑛2)∗𝑥
𝑒𝑛𝑑 𝑖𝑓 𝑒𝑛𝑑 𝑝𝑟𝑜𝑐𝑒𝑑𝑢𝑟𝑒

View: Threaded  |  Flat
+1

Comments

  • 46 posts Wed, Apr 21, 2021 at 04:30 PM

    Is this an actual problem? The big O for a recursion function is O(bd) where b is the number of branches and d is the depth and the recursion. For this problem it appears that the recursion will not reach the base case unless the value of n selected is 0 or 1.

    +0
  • 180 posts Wed, Apr 21, 2021 at 04:50 PM

    I guess the n2 means n/2. I found the same code here: https://stackoverflow.com/questions/50317996/figuring-out-the-time-complexity It's n/2 at this question. With this, it won't run indefinitely and n will be either 0 or 1 at some point

    +0
Sign In or Register to comment.