Algorithm Analysis Big-O

Question

I need some help calculating the Big-O running time.

I have attempted to do it after each problem, but not sure if it's done correctly.

Q-1: Given the following code fragment, what is its Big-O running time?

 test = 0

 for i in range(n):

        for j in range(n):

                test= test + i *j

T(n)= c1+n*(n)

= c1+n^2

O(n) ≈ n^2

Q-2: Given3 the following code fragment what is its Big-O running time?

 for i in range(n):

      test=test+1

 for j in range(n):

      test= test - 2

T(n)= c1*n+c2(n*n)

T(n)= c1*n1+c2n^2

O(n) ≈ n^2

Q-3: Given the following code fragment what is its Big-O running time?

 i = n

 while i > 0:

        k=2+2

        i = i // 2

T(n)= n*(c1+c2)

O(n) ≈n

One would say `T(n) = O(n^2)`, not `O(n) ≈ n^2` for some (unspecified) function of `n`. — chepner, Oct 03 '17 at 15:43
Your 2nd code snap identation is unclear. Is the 2nd loop nested within the first? — amit, Oct 03 '17 at 15:43
I would say `O(n^2)`, `O(n)`, and `O(n)` respectively. For Q2 Just because jyou have `2 * O(n)` doesn't make it `O(n^2)` — Cory Kramer, Oct 03 '17 at 15:44
@chepner If we're at it, `T(n)` is in `O(n^2)`, since `T(n)` is a function and `O(f(n))` is a set of funcitons/ — amit, Oct 03 '17 at 15:44
@CoryKramer The third one; `//` is a division operator in Python. — chepner, Oct 03 '17 at 15:47
Why the downvotes?! Just because you know the answer and you've taken computer science courses doesn't mean this isn't a legitimate question. And the OP has clearly tried, with explanation! What more could you want? This site is obnoxious to new users. — Matt Messersmith, Oct 03 '17 at 16:00
Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Paul Hankin, Oct 03 '17 at 16:03

score 2 · Answer 1 · answered Oct 03 '17 at 15:49

2

Q-1

You are right.

for i in range(n) is O(n), nesting means multiplication, so O(n^2) is right.

Q-2

No, sequential evaluation is addition, so two loops in a row is O(n)+O(n)=O(n).

Q-3

No, each iteration halves n, so the complexity is O(log(n)).

answered Oct 03 '17 at 15:49

sds

58,617
29
161
278

1

short and to the point – Matt Messersmith Oct 03 '17 at 15:58

amit · Answer 2 · 2017-10-03T16:55:18.760

First, let's start with your terminology, O(n)≈f(n) is not the right terminology, correct one would be to say T(n) is in O(f(n)), where T(n) is the complexity function of the code, and f(n) is the given complexity, so T(n) is in O(n^2), for example.

First code snap:
This is indeed O(n^2), your analysis is correct.

Second code snap:
This is O(n^2), assuming the second loop is nested within the first (your identation is not clear), again - your analysis is correct.
If this is not the case, then these are sequential loops - each is taking O(n), so total complexity is the addition of them, which yields O(n) as well.

Third code snap:
This is O(logn). Each iteration halves i until i reaches 0. This happens within log_2(n) steps of dividing it by two.

It's sequential loops for the second case, sorry about that. — BK Hasan, Oct 03 '17 at 16:01

Algorithm Analysis Big-O

2 Answers2

Q-1

Q-2

Q-3