When and where to use the terms: time complexity, space complexity?

Question

When and where to use the terms: time complexity, space complexity?

Navigation

#1 by (2 votes)

2

I'm using the book Data Structures: Algorithms, Complexity Analysis, and Implementations in JAVA and C / C ++ as it helps with practical examples of implementation.

In chapter 1 have the following excerpt that left me in doubt

The execution time of an algorithm will be represented by a cost function T, where T (n) is the measure of the time needed to execute an algorithm for a problem of size n. Therefore, T is called the complexity function of the algorithm. If T (n) is the measure of memory required to execute the algorithm, then T is called ' space complexity function '. According to Ziviani (2004), it is important to emphasize that T (n) does not directly represent the execution time, but the number of times a certain relevant operation is performed.

Why does the author refer to T in two different ways? it was difficult to understand this variation, is there any context in which another expression should be used?

algoritmo

asked by anonymous 14.09.2018 / 03:37

1 answer

How to rotate an img 90º occupying 100% of the element? Bar Chart in ggplo2, geom_bar ()

score 2 · Accepted Answer

Because it has to do with, two things. The complexity can be measured in these two axes: execution time and occupied space. These are the factors that matter when you create or use an algorithm. How long it takes (relatively) to run and how much memory it needs (proportionally).

Perhaps the text is mottled and creates confusion, so read:

The execution time of an algorithm will be represented by a cost function T, where T (n) is the measure of the time needed to execute an algorithm for a problem of size n. Therefore, T is called the time complexity function of the algorithm. It is important to emphasize that T (n) does not directly represent the execution time, but the number of times a certain relevant operation is performed

Do you understand this part?

Now read this new one in isolation because you still talk about complexity, but on another axis, then use the same notation, but you are talking about something else:

If T (n) is the measure of memory required for the execution of the algorithm, then T is called 'space complexity function

And I add saying that it has to do with the amount of elements and not with the effective space occupied.