CODEWITHSUNDEEP
big-ocomputer-science
Jordy
Jordy

Reputation: 1049

Determening the big-o of this example

So I got this question on my test the other day and answered the question wrong, but I have no idea if my 'new' answer is actually correct. All my classmates are not able to give me a straight answer either so that's why I'm asking you guys here.

So basically the question says, "Out of different tests, the next table has been made up, what would the big-O of the alghorithm be?". In this example the left side of the table is the amount of elements and the right side the amount of time it takes to process.

enter image description here

So my new answer would actually be O(n), because the time it takes to go through twice the amount of elements aproximately is doubled. But here I'm wondering is that actually correct? Should I be more specific in my big-O notation? Is it okay to ignore the small differences in time, and that it's not EXACTLY twice as much time?

Upvotes: 2

Views: 95

Answers (4)

Ates Yanik
Ates Yanik

Reputation: 1

I am not super sure but I would calculate it as O (n ^ 0.26)

Upvotes: 0

Patrick87
Patrick87

Reputation: 28312

If you actually divide through successive terms, the data makes it look like that when n doubles, the corresponding runtime increases by a factor that hovers around 2.2. If this is not just an accident but indicative of the real asymptotic behavior of the runtime, then it is indeed almost linear, but not quite. That is, the function may be more like this:

T(n) = 10 * 2.2 ^ (log_2(n/5000))

Table of values:

n      T(n)
5000   10
10000  22
20000  48
40000  106
80000  234
160000 515

In that case, some quick algebra shows that

T(n) = 10 * 2.2 ^ (log_2(n/5000))
     = 10 * 2 ^ (log_2(2.2)log_2(n/5000))
     = 10 * (n/5000)^log_2(2.2)
     ~ 10 * (n/5000)^1.1375

Perhaps this is a better answer, perhaps worse. It is impossible to say what the asymptotic behavior is with any finite sample, but this answer - O(n^log(2.2)) - might make more full use of all available data.

Upvotes: 0

TimoStaudinger
TimoStaudinger

Reputation: 42480

For O(n), it doesn't have to scale exactly linearly. Just the fact that the resulting graph is roughly linear is a strong indication that we are indeed dealing with a complexity of O(n).

Check out the plot of the data, that makes the linear nature pretty obvious!

Upvotes: 1

developer_hatch
developer_hatch

Reputation: 16224

Exactly as you say "O(n), because the time it takes to go through twice the amount of elements aproximately is doubled" because the "n" in O(n) is a function, and it doesn't mean exactly a relation 1 to 1 in time, it's O(n) if the speed goes linear, and could be linear if the time is (n * 1/2 + 1) or (n * 2) or (n + 1) by element in time. So your answer now is correct.

Upvotes: 3

Related Questions