Self-Doubt

Question

int main()
{
    int i;
    for(i=1;i<=n;i++)
    f(i);
}
void f(int n)
{
    int A[n];
    int j;
    for(j=1;j<=n;j++)
    cout<<j;
}

What will be the time and space complexity of the following code snippet ?

Answer 1

f(1) will execute 1 time

f(2) will execute 2 times

f(3) will execute 3 times

..f(n) will execute n times

The time complexity of the program is 

1+2+3...+n=$\frac{n(n+1)}{2}=O(n^{2})$

instead of f(i) we can replace it and new program would look like

for(i=1;i<=n:i++)

   (forj=1;j<=i;j++)

      count<<j;

And this is O(n²) code segment.

Space complexity will be O(n) in worst case because say from n/2 to n iterations, each time we need an array of size O(n) and after the function is over, whole stack allocation (and in this stack allocation resides the array A[]) gets popped off.And we shouldn't be requiring more than O(n) space for this program.

Comments

Thanks Sir

---

Please don't call me sir.

Answer 2

Time Complexity:

Clearly, for $f(i) $,

$T(i) = O(i)$

Now, we have to see how many times $f(i)$ is called for $1 <= i <= n$ and then add the corresponding execution times of each of the $f(i)$'s:

$f(1) , f(2) , f(4) , f(8) ,.... , f(2^{k})$

such that $2^{k} <= n < 2^{k + 1}$

Adding the corresponding times of execution:

$T(1) + T(2) + T(4) + T(8) + ..... + T(2^{k})$

$= O(1 + 2 + 4 + 8 + ..... + 2^{k})$

$= O(2^{k + 1} - 1)$

$= O(2^{k + 1})$

$= O(2.2^{k})$

$= O(2n)$

$= O(n)$

Space Complexity:

For $f(i)$, the main requirement is to allocate space to $A[i]$ which is $O(i)$.

But once the function $f(i)$ has completed its execution, the space allocated to it is freed.

That means, next when we call $f(i + 1)$, $f(i)$ would not be occupying any space.

So, the maximum space required will be by the last function call: $f(2^{k})$ such that $2^{k} <= n < 2^{k + 1}$

So,

$Space(n) = O(2^{k}) = O(n)$

Answer 3

f(1)   ---n

f(2)   ---n

f(3)   ---n

.

.

.

f(n)   ---n

Time Complexity ----->  O(n²)
 

Space Complexity  ---> O(1)  no stack records no space req (like array of n var)