# Algorithm 1

for i=1..n
j=1
while j*j <= i:
j = j + 1


Since the outer loop is going to n and the inner loop is going to sqrt(n). My guess is that it is Θ(n^2)

$$\sum_{i=1}^{n} O(1) \sum_{j=1}^{\sqrt n}O(1) = \sum_{i=1}^{n} \sqrt j*\sqrt j = \theta(n^2)$$

Thought process for the summations: number of terms * max term

# Algorithm 2.

for i=1..n
j=2
while j <= i
j = j * j


j performs similar to a log function. Since the outer loop is n. My guess is $$Θ(n\log n)$$

$$\sum_{i=1}^{n} O(1) \sum_{j=2}^{\log n}O(1) = \sum_{i=1}^{n} (\log n -2) * O(1) = \theta (n * (\log n -2)) = \theta (n\log n)$$

# 1

For the first case, you had the right idea, but just had some algebra mistakes.

for i=1..n
j=1
while j*j <= i:
j = j + 1


Let $$T(n)$$ be the time complexity. $$T(n) = \sum_{i=1}^n\sum_{j=1}^\sqrt{i}1\leq \sum_{i=1}^n\sqrt{n}=\leq n^{3/2}$$ $$= O(n^{3/2})$$

# 2

I'm assuming you meant the pseudocode below since it is more analogous to your first case (I believe the pseudocode you posted has the same complexity). You are correct though, it is $$O(n\log n)$$ for the reason you described.

for i=1..n
j=2
while j <= i
j = j * j

• Firstly, I just want to say thanks! Secondly, I did mean the one I had up there for 2 :) Sep 25, 2019 at 11:50
• Firstly, you seem to have an syntax error up there (for 1=1..n should likely be for i=1..n)! Secondly (if my assumption with i=... is correct), his answer is still correct (it doesn't make a difference in O/Theta notation, whether j is bounded by i or n). Sep 25, 2019 at 13:36
• @oerpli yes that is what I meant when I said his original pseudocode would have the same complexity :p Sep 25, 2019 at 13:38
• @BryceKile can'y you make a case for $\theta (n \log \log n)$ for the algorithm you proposed for Algorithm 2??? Sep 26, 2019 at 10:59
• @ThomaBonparte stackoverflow.com/questions/21152609/… Sep 26, 2019 at 12:02