#Logarithmic Time Complexity Explanation

1 messages · Page 1 of 1 (latest)

unique rockBOT
#

@subtle frost has a question:

brazdenboyglass

How do you log(n) in big O notation

#

<@&987246399047479336> please have a look, thanks.

#

Here is an AI assisted attempt to answer your question 🤖. Maybe it helps! In any case, a human is on the way 👍. To continue talking to the AI, you can use </chatgpt:1108714622413963314>.

#
TJ-Bot
How do you log(n) in big O notation

Logarithmic time complexity, denoted as O(log n), is a time complexity where the running time of an algorithm increases logarithmically with the size of the input data. This means that as the input data grows, the time taken to execute the algorithm grows at a much slower rate compared to linear or quadratic time complexities.

To understand how log(n) works in big O notation, you can think of it in terms of binary search algorithms. In a binary search, each comparison reduces the search space in half. This means that for an input size of n, you can find the target value in log(n) comparisons.

For example, if you have an array of size 8 and you perform a binary search to find a specific element, at most 3 comparisons will be needed (log2(8) = 3). If you double the size of the array to 16, it will still take only 4 comparisons to find the element.

Therefore, when an algorithm has a logarithmic time complexity, it means that its running time grows logarithmically as the input size increases. This type of complexity is considered very efficient and is often found in algorithms that divide the problem space in half with each step.

In summary, log(n) in big O notation indicates an algorithm with logarithmic time complexity where the running time grows at a slower rate compared to linear or quadratic complexities as the input size increases.

- AI generated response
trim relic
#

@subtle frost logarithmic is the opposite of exponential. when you have exponential time, the time taken will increase dramatically as the number of inputs increase

#

for small data sets, exponential it not that bad. but for larger sets, you see the cost of an O(n^2)

for O(log n), its the opposite. as the number of inputs increases, the time taken only increases a small amount. you really start to see it's benefit with large data sets, as the cost to use more elements doesnt increase much

#

exponential is blue, log is red.

for exponential

  • with 2 elements, the algorithm takes 4 seconds
  • with 3 elements, the algorithm takes takes 8 seconds
  • with 4 elements, the algorithm will take 16 seconds

the time it takes is doubling, even though the amount of input isnt doubling

#

log is the opposite:

  • with 2 elements, it takes 1 seconds
  • with 3 elements, it takes 1.5 seconds
  • with 4 elements, it takes 2 seconds