I am having difficulty answering the following questions relating to the use of threading.

Question 1 is of relating to the possibility of a local storage per thread and a global storage accessible to all threads. Consider the following scenario; A program creates a series of threads each with their own local storage, kind of like a mutex system except for that no thread can access another's memory, and a square matrix stored in global storage which is accessible to all threads. When the space complexity of the following program is calculated, is the space complexity (# of elements in the square matrix)2 + (local storage of finishing thread) or (# of elements in the square matrix)2 + (local storage of all threads at the time that the finishing thread completed)?

Question 2 relates to timing threads to go at a very precise rate. Consider the following scenario; A program creates a series of threads that continually add a random set of elements to their local storage. The program finishes and returns the thread that received the shortest number of elements in its random set. If one thread was to go faster than another, the program would be incorrect. Is there a way to "lock" the threads to go at the same speed?

Any help on the answering of these questions would be appreciated. Please comment if additional info is required.

  • 1
    $\begingroup$ These should be posted as two separate questions, I think: they're not very closely related. $\endgroup$ Commented May 15, 2014 at 15:08

1 Answer 1


I will answer Question 1. As @DavidRicherby said, you should post the other question separately.

The space complexity is the maximum amount of space required while the algorithm is running. So it certainly would be more than the (number of elements in matrix) + (local storage of just finishing thread). It might be the total storage of all the threads at the time the program finished but only if (a) you haven't already exited any of the threads, and (b) none of the threads freed up a bunch of memory just before the program finished.

You also need to be careful to not overcount. As described here there are a lot of optimizations that allow you to reuse space, so you can't just sum up all the memory allocated by every thread that ever existed. You really need to figure out the point in time during your program execution when the most memory is in use.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.