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

1 Answer 1

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$
2
  • $\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, 2015 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$ Oct 29, 2015 at 17:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .