Played around with programming in different languages over the years. Trying to unlearn old habits while keeping those worth keeping. Doing algorithms contests, bronze medal from IOI.
Your understanding of limits is correct. As n approaches infinity, c can get closer and closer to 3. n³ is bigger than n² by a factor of n, which means the 2n² part gets closer and closer to negligibly.
Now, the definition of big O states:
T(n) belongs to O(n³) if there exists some finite constants c and n_0 for which every n >= n_0 satisfies T(n) <= c*n³
If n_0 is 1, then c has to be 5, as you showed.
As n_0 gets bigger, c can get closer to 3, as you also showed.
The important part is that there exists some pair of n_0 and c satisfying the requirement.
In fact, if one such pair exists, infinite pairs exist!
Played around with programming in different languages over the years. Trying to unlearn old habits while keeping those worth keeping. Doing algorithms contests, bronze medal from IOI.
.
The O(n²) solution is trivial, but see if you can come up with one that's O(nlog n) (Hint: sorting). I have posted a python solution in the comments, with explanations. Good luck!
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Your understanding of limits is correct. As n approaches infinity, c can get closer and closer to 3. n³ is bigger than n² by a factor of n, which means the 2n² part gets closer and closer to negligibly.
Now, the definition of big O states:
T(n) belongs to O(n³) if there exists some finite constants c and n_0 for which every n >= n_0 satisfies T(n) <= c*n³
If n_0 is 1, then c has to be 5, as you showed.
As n_0 gets bigger, c can get closer to 3, as you also showed.
The important part is that there exists some pair of n_0 and c satisfying the requirement.
In fact, if one such pair exists, infinite pairs exist!
Hope this helped, cheers
Ok I think I get it now.
Thank you very much!^
I'm glad to hear!
If you want some practice, do have a look at a challenge I uploaded
Remove terrible bus routes (find an algorithm)
Håvard Krogstie ・ Mar 9 ・ 2 min read
The O(n²) solution is trivial, but see if you can come up with one that's O(nlog n) (Hint: sorting). I have posted a python solution in the comments, with explanations. Good luck!