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

  • 99 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
  • 215 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.