2,108 views
2 votes
2 votes

Time Complexity, according to me it should be n^5Time complexity

3 Answers

0 votes
0 votes
O(n^5)
0 votes
0 votes

Take any arbitrary value of i, let i=4

Then inner most statement runs as--

(1to4 + 1to 8 + 1to 12 + 1to 16 ) due to the condition j(mod) i becomes true. +

For j=(1,2,3,  5,6,7  ,9,10,11,  13,14,15) i.e. 3*4 times due to j loop only.

Therefore for any i=m statements runs

m* (m-1)+ m(1+2+3+.....+m) times

=m*(m-1)+m{m(m+1)/2} times

So for i=1 to n

=> Σ(m*(m-1) + m{m(m+1)/2} )   [m=1 to n]

=> leading term =(Σ(${m^3}$))=O(${n^4}$).

edited by

Related questions

0 votes
0 votes
0 answers
2
0 votes
0 votes
1 answer
3
NeelParekh asked Jul 27, 2023
263 views
If an array is split in the form of increasing and decreasing order then what is TC to find minimum element in the array?
2 votes
2 votes
1 answer
4
h4kr asked Dec 30, 2022
432 views
What is the correct time complexity in $\theta()$ ?