-1
$\begingroup$

What is the time complexity Big-O of this algorithm?

, The first assumption it's O(N * lg N) but it is not correct, why?

        count = 0
        for i = N : 1 {
            for j = 0 : i {
                count = count + 1
                j =  j + 1
            }
            i = i/2
        }
        print(count)
$\endgroup$
6
  • 1
    $\begingroup$ Big-O of what? Time complexity or count or space complexity? $\endgroup$
    – Mr. Sigma.
    May 13, 2020 at 6:54
  • $\begingroup$ What language is this? $\endgroup$ May 13, 2020 at 8:23
  • $\begingroup$ @Mr.Sigma. I am asking about the Time complexity $\endgroup$
    – 0xh3xa
    May 13, 2020 at 12:53
  • $\begingroup$ @greybeard i decrement the half each iteration. will start from N, N/2, N/4, N/8,....,N/N $\endgroup$
    – 0xh3xa
    May 13, 2020 at 12:55
  • $\begingroup$ It’s clearly n^2 because I iterates from n down to 1, and changing I doesn’t affect this. $\endgroup$
    – gnasher729
    May 14, 2020 at 7:06

7 Answers 7

4
$\begingroup$

The second for-loop while be executed N + N/2 + N/4 +....+ N/N

, the first for-loop decides how much the second for-loop will be executed.

When i = 0, j loops until N

, i = N/2, j loops until N/2

, And so on

, The Big O notation of N + N/2 + N/4 +....+ N/N will be O(N)

$\endgroup$
3
$\begingroup$

The runtime for this algorithm is $\Theta(n)$.

By rewriting the iterative formula as a recurrence relation $T(n)=T\left(\frac{n}{2}\right) + n$ we can use Master Theorem to analyze the runtime. The recursive equation doesn't meet the criteria for the first or second cases but it does meet those for the third, meaning $T(n)=\Theta(f(n))$ where $f(n)$ is the amount of work done at each iterative level of the algorithm; in this case $f(n)=\Theta(n)$ and so $T(n)=\Theta(n)$.

$\endgroup$
2
  • $\begingroup$ Well, $\Theta(n) \subset O(n \lg n)$. $\endgroup$
    – greybeard
    May 13, 2020 at 8:31
  • $\begingroup$ @greybeard Yes, that's true, but it also holds that $\Theta(n)\subset O(2^n)$ but that doesn't make $O(2^n)$ a useful upper bound for the algorithm's runtime. You're absolutely correct in your assertion but it's a bit like being asked what the upper bound for the height of a human being is and answering "50 meters". Sure, it's true, but it doesn't actually tell me much about how tall people are. $\endgroup$ May 13, 2020 at 10:44
1
$\begingroup$

*Cough* Nice homew... Ahem

It's O(N*log(N)) because the outer loop runs log(N) times (i from N to 1, dividing by 2 each time) and the inner loop runs i times (so N times the first time for example, then less).

$\endgroup$
5
  • $\begingroup$ The outer loop run from N, N/2, N/4,..N/N $\endgroup$
    – 0xh3xa
    May 12, 2020 at 21:27
  • $\begingroup$ Yes, and N, N/2, N/4... to 1 is log(N) (in base 2) steps. $\endgroup$
    – user102180
    May 12, 2020 at 21:28
  • 1
    $\begingroup$ Imagine N is 2^32 (approximately FOUR BILLION) and log(N) = 32. Outer loop will run 32 times. Inner loop will run 2^32 times, 2^31 times, 2^30 times... So inner loop is N. $\endgroup$
    – user102180
    May 12, 2020 at 21:33
  • $\begingroup$ the inner loop will n, n/2, n/4, n/8, .... $\endgroup$
    – 0xh3xa
    May 12, 2020 at 23:06
  • $\begingroup$ the inner doesn't iterate n each time $\endgroup$
    – 0xh3xa
    May 12, 2020 at 23:08
1
$\begingroup$

there is two loops .. the inner loop over O(N) numbers(0 to i at most i=N) and the outer one starts the loop from N and slice it by two in each iteration (N -> N/2 -> N/4 ..) therefore the big-O of the algorithm is O(Log(N)*N).

$\endgroup$
3
  • 1
    $\begingroup$ the inner loop will n, n/2, n/4, n/8, .... $\endgroup$
    – 0xh3xa
    May 12, 2020 at 23:07
  • $\begingroup$ you are right .. this big-O not the asymptotic..i edited my answer $\endgroup$
    – Obida Asad
    May 13, 2020 at 0:19
  • $\begingroup$ How does your argument for (runtime in) $O(\log N \times N)$ answer assumption [O(N * lg N)] is not correct, why? $\endgroup$
    – greybeard
    May 13, 2020 at 8:27
0
$\begingroup$

A more practical approach:

The most executed statements in this example is the ones inside the innermost loop, for example

count = count + 1

This statement counts how many times it is executed, which means that the total runtime is approximately proportional to the output.

So, try to run this program with various inputs and see what the output is. I don't know this language, so I don't know the exact semantics, but it seems that the approximate count is $2N$.

Knowing this answer should put you on the right track to finding out why.

$\endgroup$
0
$\begingroup$

When the value of i is N, the inner loop will run N times

Then, the value of i becomes N/2, so the inner loop will run N/2 times

then, the value of i becomes (N/2)/2, so the inner loop will run N/4 times

This continues till the value of i becomes 1, so the total time complexity is : $$N + N/2 + N/4 + N/8 + ....... + 1$$

Or $$1 + 2 + 4 + 8 + 16 + ..... N/2 + N$$

Total number of terms in this is t= $$log2(N)$$ ignore lower terms(constants) in the calculations below(for the sake of Big O Notation):

summing up we get $$2^t-1 = log(N)$$ Thus, time complexity is O(N)

$\endgroup$
0
$\begingroup$

Forget about the outer loop. Just remember that on it's way from $N$ to 1, $i$ gets divided by $2$ on each iteration.

Now, on the first iteration of the second loop, $j$ will go from $0$ to $N$, and so we will have $N-0+1 = N+1$ steps. On the second iteration, $j$ will go from $0$ to $\frac N2$, so we will have $\frac N2 + 1$ iterations. You can see how this evolves: $(N + 1) + (\frac N2 + 1) + (\frac N4 + 1) + \dots + 2.$

For simplicity, let's remove the $1$'s from each term because their effect on $N$ is insignificant as $N \rightarrow \infty$.

Now, all you have to do is sum up $S = N + \frac N2 + \frac N4 + \dots + 1$.

Factorizing $N$ gives $S = N(1 + \frac 12 + \frac 14 + \dots +\frac {1}{2^n}) = N \sum_{k=0}^{n} (\frac 12)^k$.

The result of the sum (using the formula of a finite geometric series) is $2(1-(\frac 12)^{N+1})$. As $N\rightarrow \infty$, this sum tends to $2(1-0) = 2$.

Finally, we have that $T(N) = \Theta(2N) = \Theta(N)$.

$\endgroup$
3
  • $\begingroup$ i gets divided by 2 on each iteration What will be the value of $i$ at the start of the next iteration (if any), and how do you know? $\endgroup$
    – greybeard
    May 13, 2020 at 23:02
  • $\begingroup$ @greybeard From the given code: i = N : 1. It's obvious, i is $N$ on the first iteration. Before the start of the second, we have i = i/2, hence the value of i on the second is $\frac N2$. Are you sure you understand the code? $\endgroup$
    – user821
    May 14, 2020 at 5:14
  • $\begingroup$ (Values from start value N halved in each iteration could have been gleaned&assumed even by me from the the inner for-loop showing explicit increment of the control value. I assumed implicit decrement in the outer one - not that that would have changed the tight asymptotic boundary unless it was the type "the control variable takes on every value from start to end in turn unless stated otherwise in the for construct".) (Know for-right-part?) $\endgroup$
    – greybeard
    May 14, 2020 at 5:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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