-1

I'm trying to learn and understand how to find tightest big O notation. Here I need to find tightest big-O notation for these algorithms, and I did the calculating for the running time.

Now I need to prove or find the tightest big-O notation but I'm not sure where should I start.

1) 2 n^2+ 2 n +2= O(n^2)

2) 6 n log n +4n +2 =O (n log n)

3) 6 X1000 n+ 4n +2 = O(n)

Not really sure how to solve this part from question. How I make sure my equation is tightest big-O?

Any help or suggestions would be greatly appreciated, thanks!

Jaap
  • 81,064
  • 34
  • 182
  • 193
stephan
  • 37
  • 8
  • Are you looking for Big Theta? I'm not really sure what you are asking. Is this a homework question? http://stackoverflow.com/questions/10376740/what-exactly-does-big-%D3%A8-notation-represent – Scotty Waggoner Sep 26 '16 at 05:33
  • yes this is the question finding tightest big O notation . I think it's to find Thita as you said. – stephan Sep 26 '16 at 05:37

1 Answers1

0

Simply said : You take the one that is "highest" term and remove all constant multipliers.

The reasoning behind this is that as n grows, the highest term will contribute the most to the total time. So rest will become negligible for big enough n. And removing the constant multipliers is in definition of time complexity.

Euphoric
  • 12,645
  • 1
  • 30
  • 44
  • Could explain more I removed all constant and remain only big which is LHS . IS there any way to prove tightest big-O notation? – stephan Sep 26 '16 at 06:02