I'd like to ask you about the time complexity of data structure

In an algorithm with time complexity of O(n^{2), if the number of inputs has doubled, what trend does the execution time increase?}

^2)'s

From this

(2n)² = 4n²

²²

Is this four times the answer?

I keep getting confused between unchanged and 4x.

I'm confused with the part where you throw away the coefficient of the highest port when you make the Big O notationㅠ<

data-structure time-complexity big-o

2022-09-20 19:55

1 Answers

In O(n²), n² represents the highest order of magnitude of T(n) in the worst case scenario. where n is the number of data.

²²

I think the number of inputs in the question means the number of data n, right?

The approximate computation from Big O is n², and if the original number of data was x, the computation would be x² if the number of data was doubled to 2x, the computation would be (2x)^{2^{=4x^2.}}

²²²²

Eventually, x² became 4x², so the running time is quadrupled.

²²

However, the sentence of the question seems to be misleading. If the question asks for a change in execution time, I think it will be right that there is no change in Big O because the "change in execution time" is big, and if the question is just asking for an increase in "execution time" itself, it will be four times right.

2022-09-20 19:55

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656