3 replies to this topic

[infimum]

Hi,

How can i determine the orders of growth of the time and space complexities?

For example in this code:

(define almony
(lambda (n m)
(if (< n 1)
0
(+ m (almony m (/ n 2))))))

Thanks...

[WingedPanther]

You could rewrite the function as a recursive procedural function (in C, for example), and compute the complexity there.

[infimum]

I'm sorry, i don't understand. What do you mean " rewrite as a recursive procedural function"? (and this is my first programming language, so i dont no nothing about C).

However, I think that the space complexity is O(m), because there is a pending operation, am i right? And what about the time complexity?

Thanks again for your time.

[WingedPanther]

From what I can tell (roughly), space complexity will be less than O(m), and time and space complexity will be the same. Also, the values of both m and n are relevant.

Have you traced through a few calls, such as (almony 10 20) and (almony 20 20) and (almony 100 100)?