CODEWITHSUNDEEP
algorithmtime-complexitycomplexity-theoryasymptotic-complexitybig-o
NM2
NM2

Reputation: 127

Find the asymptotic running time of the following code sections

Find the asymptotic running time of the following code sections. The answer should be the terms of O and Theta.

enter image description here

I thought about, Theta(n^(1.5)),But im not sure about this. What do you think ?

Upvotes: 1

Views: 165

Answers (1)

Am_I_Helpful
Am_I_Helpful

Reputation: 19168

The inner loop runs for n1/2(square-root of n) times for each iteration of the outer-loop.

The outer-loop runs for n times.

So, the net complexity of running the program would be O(n*n1/2) = O(n3/2) = O(n1.5).

Also, since providing a tighter bound would round it up to Big-Theta(n1.5) time complexity.

So, the time-complexity of the code = Θ(n^1.5).

Upvotes: 2

Related Questions