retagged by
494 views

3 Answers

Best answer
0 votes
0 votes

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(n2) 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.

selected by
1 votes
1 votes

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)$

0 votes
0 votes

f(1)   ---n

f(2)   ---n

f(3)   ---n

.

.

.

f(n)   ---n




Time Complexity ----->  O(n2)
 

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

reshown by

Related questions

0 votes
0 votes
3 answers
1
Nisha Bharti asked Sep 26, 2022
681 views
What is the time & space complexity of this algorithm?Main(){ for(i=n; i>10; i=i^1/4) { for(j=201; j<n^3; j=j+400) ...