I've never understood how to handle space analysis. I understand that it mostly depends on a part that varies depending on the instance, but I don't see it. I understand the time analysis for programs, but space doesn't seem as easy to figure out.
If someone could just try to explain what to look for when dealing with space analysis, that would be great.
Find the best theta() for the worst case space required by the following sets of code give
a.
vector <vector<int> > v(n); // Creates a vector of vectors
for (int i = 0; i< n; i++)
v[i].resize(n); // allocates space for each vector
Here's my look on this part. The creation of the vector of vectors takes space. And then they allocate the space for each. So, I figure that's all the space needed for this program, I just don't see how I can put a number to it. I mean, it could be that it's n vectors of n size, so my guess would be n*n
but that's more of a guess then anything.
b. foo(n) where
int foo(int n)
{
if (n < 2)
return 73;
else
return foo(n/2);
}
For this one, since it's recursive, I would assume it's n times a constant, thus leaving it at n.