159 views

1 Answer

5 votes
5 votes

NOTE : For Calculating the time complexity implemented using loops then try to analyze

how many time #some code is running.


The given loop is nested loop.

Outer Loop is going from i = 1 to i = N and with each iteration it is incremented by 1 only.


Inner loop is going from j = 1 to j = $i^{2}$ and with each iteration it is incremented by the value of i.


 

For i =1

    j = 1 $\rightarrow$ 1 (Increment by +1)

       Total Execution of #some code in this Iteration = 1


For i =2

    j = 1 $\rightarrow$ 4 (Increment by +2)

       1 $\rightarrow$ 3 $\rightarrow$ 5

       Total Execution of #some code in this Iteration = 2


For i =3

    j = 1 $\rightarrow$ 9 (Increment by +3)

       1 $\rightarrow$ 4 $\rightarrow$ 7 $\rightarrow$ 10

       Total Execution of #some code in this Iteration = 3


For i =4

    j = 1 $\rightarrow$ 16 (Increment by +4)

       1 $\rightarrow$ 5 $\rightarrow$ 9 $\rightarrow$ 13 $\rightarrow$ 17 

       Total Execution of #some code in this Iteration = 4


For i =5

    j = 1 $\rightarrow$ 25 (Increment by +5)

       1 $\rightarrow$ 6 $\rightarrow$ 11 $\rightarrow$ 16 $\rightarrow$ 21 $\rightarrow$ 26

       Total Execution of #some code in this Iteration = 5


Similary,

For i =N

    j = 1 $\rightarrow$ $N^{2}$ (Increment by +N)

       Total Execution of #some code in this Iteration = N


 

So, total number of times #some code is executed :

1 + 2 + 3 + 4 + 5 + - - - - - - - - + N

$N(N+1)/2$

$\simeq$ $O(N^{2})$

edited by

Related questions

319
views
1 answers
0 votes
24aaaa23 asked Oct 1, 2023
319 views
Let G1 (V, E) be a connected undirected graph and G2 (V1, E') be the subgraph of G1. Weights are assigned to the edges of G1.W(e) = 0; if ... will be additional time complexity (strict upper bound) to determine if G2 is connected or not.
426
views
1 answers
0 votes
Overflow04 asked Oct 9, 2022
426 views
how O($n^{2}$) in the last.(in the given solution).
304
views
0 answers
0 votes
Overflow04 asked Oct 9, 2022
304 views
Is it really coping operation will take O(n).Does copy is done character by character.means simple code like (in c++) for(int i=0;i<n;i++){s=s;}will take O($n^{2}$)