CODEWITHSUNDEEP
big-o
Jacob
Jacob

Reputation: 3801

Big-O of algorithm

I have a quite simple problem, however I am a bit unsure of what the actual runtime (e.g. Big-O) is of this.

The program looks like this.

n <- user input
for i=1 to n
    foo(i)

foo a:
for i=1 to a
    foo2()

foo2 does an near constant amount of work which is not going to be significant.

What is the Big-O of this?

Upvotes: 0

Views: 98

Answers (2)

user3072164
user3072164

Reputation:

(Assuming the inner function foo2() is Θ(1))

It's Θ(n^2), because the outer loop is executed once for all i=1...n with the inner loop being iterated i times per outer loop iteration, that makes in total sum(i) from i=1 to n executions of foo2(), which is equal to (n+1)*n/2 = 1/2*n^2+1/2*n times.

Θ(n^2) implies O(n^2).

Upvotes: 1

Commander Coriander Salamander
Commander Coriander Salamander

Reputation: 620

For each integer 0 <= i <= n, there's another loop which goes 0 <= j <= i.

So, the i-th integer requires i calls to foo2().

Over n integers, this adds up to an average of (n / 2) extra calls to foo2() per integer -

n + (n - 1) + ... + 1 + 0 is the same as

n + (n - 1 + 1) + ... + (n - n/2 + n/2), or

n * (n / 2).

Since the upper bound on complexity is n^2 / 2, its growth will happen as quickly as n^2 - so the complexity is O(n^2).

Upvotes: 2

Related Questions