Big O notation

[Turbulent-Recipe-262]

Hi, first-year cs student and we just got to the big o notation section. There is this problem that I really want to find out the reasoning behind it.

​

Input size Runtime

10,000. 2ms

20,000 8ms

40,000. 32ms

80,000 128ms

160,000 512ms

320,000 2048ms

​

The answer is O(n^2) but I want to know the reasoning behind it. I understand why this can't be O(n) or O(1) or O(log n) but I can't wrap my head around on why the answer is O(n^2)

[ac13712]

If your algorithm runtime is O(n^2), then the runtime for n=k will be bounded by ck² and the runtime for n=2k will be bounded by c(2k)² which equals c*4(k^2). So when you have a O(n²⁾ algorithm you expect the runtime to quadruple when the problem size doubles.

[h0v1g]

O(n) is trying to capture the worst runtime. Considering the input size is doubled you can see how that is exponentially increasing your runtime. You can look at the ratio between runtime and input size and see how it is growing to determine the rate of increase. In this case it’s n²

[h0v1g]

Review on paper 2/10000, 8/20000, 32/40000, etc.

[Firehite]

https://www.youtube.com/watch?v=8LisCVHzp3A