0
$\begingroup$

I'm not exactly sure what the difference between these two are. Basically I have a problem that I describe how to complete recursively and then I have so give the asymptotic running time and asymptotic space required for it. I know these have to with giving the Big-O notation but I'm not certain and don't really understand the difference between the two.

$\endgroup$
0
$\begingroup$

Asymptotic running time is a time your program need to compute result for an input of lenght $n$.

Asymptotic space required is how many space will your program use in order to compute result for an input of lenght $n

Both of them should be written in O-e.t.c. notations.

For example if for input of lenght $n$ you need to do at least $5 n$ computational steps your time will be O(n).

If you need to create 3 matrices $n\times n$ in size each in order to compute the result for an input of length $n$ you require O(n^2) space.

$\endgroup$
  • $\begingroup$ so i'm assuming running time would be answered in Big-O notation but how would you answer how much space required? like how much space a in memory? Can you explain that more? $\endgroup$ – PeteGuru Oct 29 '15 at 17:15
  • 1
    $\begingroup$ If you have a fixed number of n x n matrices, that will take $O(n^2)$ space, no matter how long the program takes to run. $\endgroup$ – marty cohen Oct 29 '15 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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