CODEWITHSUNDEEP
algorithmanalysisbig-o
csonq
csonq

Reputation: 25

Big Omega Analysis

I've been struggling to understand the best possible running time of this:

for t = 1 to n
    sum = 0

    for i = 1 to t
        sum = sum + x[i]

I understand the first loop will go n times. It's the inside loop that I struggle with. The inside loop will go n(n+1)/2 the first time but n(n+1)/2 -1 the next time. I'm not sure how to translate this to best running time.

I could use a push in the right direction if possible. Thank you!

Upvotes: 1

Views: 108

Answers (2)

Ulrich Eckhardt
Ulrich Eckhardt

Reputation: 17415

In order to visualize this, I take the approach of imagining an area filled with squares or a volume filled with dice in more complex cases. Each square represents an atomic step. All steps of an iteration of the the outer loop are put on the same row. For your case, it looks like this:

t=1 #
t=2 ##
t=3 ###
t=4 ####
t=5 #####

As you can see, these form a triangle, who's height is N and who's width is also N. If you now count the squares (N * (N + 1) / 2) you have the number of iterations of the inner loop. Multiplying that and dropping irrelevant terms gives you the complexity Θ(N*N).

Upvotes: 1

Compass
Compass

Reputation: 5937

You're adding a small bit of complexity to your attempt to analyze O(n). That is likely why you're confused.

We know that the outer for loop 1 to t is linear. The inner loop runs more over time. At t = 1, it runs once, at t = n, it goes n times.

What is the average amount of times we run through the for loop?

avg = (1 + n)/2

This is the value you found, though you tried to iterate through it. All we need is the average for our calculations.

Because 1 is relatively insignificant to n for high values of n, we can approximate this to n/2.

So the outer loop runs n times. The inner loop runs n/2 times.

n * n / 2 = 0.5n^2

Since we normally ignore most multiplicative values, we can say that O(n) = n^2

Upvotes: 0

Related Questions