1
$\begingroup$

I have a few algorithms and am trying to determine their complexity using Big Theta notation:

for i in 1..n
    for j in 1..i
        for k in 1..j
            O(1)

while n >= 1
    O(1)
    n /= 2

while n >= 1
    for i in 1..n
        O(1)
    n /= 2

I'm looking for their complexities in terms of $n$. Trying to tackle the first, I'm trying to work my way up from one loop to three (t means big theta):

for i in 1..n - t(1 + 1 + 1 + ... + 1) = t(n)
    O(1)

for i in 1..n - t(n)
    for j in 1..i - t(1 + 2 + 3 + ... + n) = t(0.5n(n-1))
        O(1)

And from here I'm not sure how to proceed as the arithmetic is complicated.

The options for a solution are $\Theta(c)$, $c \in \{1, n, n^2, n^3, 2^n, n!, \log n, n \log n\}$ but already I feel like I'm outside that scope. I'm also not even sure what $\Theta(\log n)$ and $\Theta(n \log n)$ mean for an algorithm.

These questions are marked fairly low, so I wonder if I'm overthinking it or missing a simple methodology to determine complexity.

Were the loops strictly 1..n for all three, I know it would be $\Theta(n^3)$ but not when loop bounds depend on each other.

From my loose understand of complexity, I think $f(n) \in O(g(n))$ means $f(n)$ is dominated by $g(n)$ and $f(n) \in \Omega(g(n))$ means $g(n)$ is dominated by $f(n)$. I think $f(n) \in \Theta(g(n))$ means they're equivalent.

$\endgroup$
  • $\begingroup$ Hint: For the first one, try a triple summation and use standard sum formulas. $\endgroup$ – Michael Burr Jun 30 at 3:16
1
$\begingroup$

First one:

$$\sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=1}^{j}1=\sum_{i=1}^{n}\sum_{j=1}^{i}j=\sum_{i=1}^{n}\frac{i(i+1)}{2}$$$$=\frac{1}{2}\sum_{i=1}^{n}i^2+\frac{1}{2}\sum_{i=1}^{n}i=\frac{1}{12}n(n+1)(2n+1)+\frac{1}{4}n(n+1)=\Theta(n^3)$$

Second one:

Number of steps is $k$ where $2^k\le n<2^{k+1}$ so $k \le \log n < k+1$, so $k=\Theta(\log n)$

Third one:

$$n+\left\lfloor\frac{n}{2}\right\rfloor+\left\lfloor\frac{n}{4}\right\rfloor+...\le n+\frac{n}{2}+\frac{n}{4}+...=2n$$ And since the number is between $n$ and $2n$ it is $\Theta(n)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.