Runtime & Spatial Complexity of the Code?

[wrack]

Hi,

What is the difference between Runtime & Spatial Complexity of the Code?

And how would one calculate and describe it?

Cheers

[Andre S. Veteran]

That sounds like a homework question.

[wrack]

That sounds like a homework question.

Hi Andre,

 

I am actually preparing for an interview. What I should have done is post the code I wrote and then shows what I think the complexity is and understand from experts here.

 

Sorry if it felt like one but it is not a homework question.

 

Thanks

[Andre S. Veteran]

The complexity of an algorithm (in Big-O notation) is an upper bound on the growth rate of resources required to run it, expressed in terms of n where n is the number of elements. So it's a measure of how the algorithm scales as the problem size grows. For example, the growth in resources required to run an O(n^²) algorithm is no faster than the growth of the amount of elements squared.

 

Time complexity then refers to how much time is required to run the algorithm as a function of the number of elements. Space complexity refers to how much memory is required.

 

You can find this information explained in a variety of ways all around the web, for instance http://www.leda-tutorial.org/en/official/ch02s02s03.html

[wrack]

Thanks Andre. I have read some of them. I am going to post the code soon so I can explain what I think and then understand from you/anyone else on if that is correct or not.