Running time of algorithm (effect of j*j in for loops) - Theta Runtime In Theta notation what are the running times of these algorithms?
Algorithm 1
for i=1..n
    j=1
    while j*j &lt;= 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 &lt;= 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 &lt;= 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 &lt;= i
        j = j * j