33951

Running Time Complexity of O (n / 2)

<h3>Question</h3>

I once understood this but not anymore. Lets say I have an algorithm that will return the number in the middle of an array.

for (int i = 0; i < nums.length; i++) { if (i == nums.length / 2) return nums[i]; }

The worst case of this will always be O (n / 2) right? There is no worse case than this. But how come we just conclude that it is O(n) ?


<h3>Answer1:</h3>

Big O time complexity is not about measuring the actual time an algorithm will take, it instead specifies what variables the time complexity is dependent on and what kind of relationship there is between those variables and the time complexity (ie linear, polynomial, exponential, etc).

Because constants do not effect the type of function the time complexity is they do not change the Big O value.

Note in your case the code you wrote may actually compile to something with constant time if the compiler is smart enough to note all iterations of the loop are dead but one.

来源:https://stackoverflow.com/questions/40250606/running-time-complexity-of-o-n-2

Recommend

  • Exact-match, case-insensitive match without normalization in Elasticsearch 6.2
  • Is it possible to parallelize awk writing to multiple files through GNU parallel?
  • TensorFlow with Docker
  • explode() doesn't separate a string by spaces?
  • Prevent spaces in URL showed like %20
  • How to prevent grid-row span from changing column placement?
  • How to add JButton on JScrollPane?
  • R with roxygen2: How to use a single function from another package?
  • Include manually-added lines to ggplot2 guide legend
  • Is there any easy way to do modulus of 2^32 - 1 operation?
  • Edittext keeps focus when keyboard up AND scrolling the listview
  • Is there a gcc flag to catch integer truncation?
  • Programmatically reading a Microsoft Word document
  • Is there a way to control flow of promises in linear call order?
  • URISyntaxException - How to deal with urls with %
  • Is it appropriate to wrap each navigation element in a div?
  • How to return only text after a comma in a string
  • Sync Local Microsoft MySQL database to remote mysql database scheduled daily
  • Sum multiple columns [duplicate]
  • I really do not understand mysql injection? What is it?
  • Check/Uncheck - ifChecked not working
  • Python and PHP SOAP server
  • PHP - How to access and retrieve important data from a pop3 email account?
  • Manifest marge error after migrating to androidX
  • SPOJ: GENERAL (Time limit exceeded)
  • How to position a Widget at the bottom of a SingleChildScrollView?
  • Advertising Identifier for devices lower than iOS 6.0
  • Expression.Call GroupBy then Select and Count()?
  • playing mp3 from nsbundle
  • .Net core Hosted Services guaranteed to complete
  • How to resolve this in PHPUnit where it is asking me to set KERNEL_DIR in my phpunit.xml?
  • Tensorflow Dataset API restore Iterator after completing one epoch
  • Bind selectedDates Aggregation for Calendar
  • Google App Engine backend servlet not responding
  • Make checkout phone field optional for specific countries in WooCommerce
  • Excel VBA : conditional formatting of sheet1 cells from sheet2 values in excel 2007
  • Call Microservice from another Microservice within Docker
  • Why does Rails 3 think xE2x80x89 means â x80 x89
  • Access to a Matlab gui from the web