CODEWITHSUNDEEP
big-o
richsoni
richsoni

Reputation: 4278

Simple Big-O calculation

I am aware intuitively that two for loops make an O(n^2) function, but what if the loops are unrelated. How is it expressed

For example:

for(x = 1; x < t; x++)
    for(y = 1; y < z; y++)
            do something trivial
    end
end

is the big-o of this O(t*z)? or is it O(n^2) or is it O(t^2). I have always overlooked this, but I would like to know now.

Thanks

Upvotes: 3

Views: 439

Answers (5)

Charlie Martin
Charlie Martin

Reputation: 112404

Basically it's really O(t*z), but unless there is something specific about the problem otherwise, you would normally just say O(n^2). The reasoning for that is pretty simple: assume you have t,z with t≠z. Then for any particular t,z there exists t/z which is a constant. You can factor that out, it becomes a constant in the expression, and you have n^2. O(n^2) is the same as O(t^2) for our purposes -- it's a bit more correct to say O(t^2) but most people would understand you using the generic n.

Update

Okay, sorry, let's take this a bit further. We're given t,z, both positive natural numbers with t≠z, and with no specific functional relationship between t and z. (Yes, there could be such a relationship, but it's not in the problem statement. If we can't make that assumption, then the problem can't be answered: consider, eg, that z = tx. We don't know the x, so we can't ever say what the run time would be. Consider z = st. If I can assert a functional relation might exist, then the answer is indeterminate.)

Now, by examination we can see it's going to be O(t*z). Call the function that's the real run time f(n)=n2. By definition, O(f(tz)) means the run time f(tz) ≤ kg(tz) for some constant k>0. Divide by z. Then f(t)/z ≤ (k/z)g(t), and thus f(t) ≤ kg(t). We substitute and get f(t)=t2 and renaming the variable makes that O(n2).

Upvotes: 1

hspain
hspain

Reputation: 17568

I don't know that I would consider this O(n^2) without some further information about the how the loop will be used.

If z will always be less than or equal to 1, you would get O(n) or O(1).

Upvotes: 0

Roman
Roman

Reputation: 10403

Normally two for loops inside one another is O(n^2) which is read O n squared.

Upvotes: 0

duffymo
duffymo

Reputation: 308988

for(x = 1; x < t; x++)
    for(y = 1; y < z; y++)
            do something trivial
    end
end

As written, these loops execute (t-1)*(z-1) = t*z - t - z + 1 times -> O(t*z)

Upvotes: 1

duedl0r
duedl0r

Reputation: 9424

It's O(t*z). If you have two nested loop each doing n iterations you have n^2 because of n*n :)

It's like computing the area.. for every t you iterate z times.. so it's intuitively t*z..

Or you can imagine to have a counter inside the loops.. how much will be the result?

Upvotes: 7

Related Questions