They are not equivalent: sqrt(N) will increase a lot more quickly than log2(N). There is no constant C so that you would have sqrt(N) < C.log(N) for all values of N greater than some minimum value.
An easy way to grab this, is that log2(N) will be a value close to the number of (binary) digits of N, while sqrt(N) will be a number that has itself half the number of digits that N has. Or, to state that with an equality:
log2(N) = 2log2(sqrt(N))
So you need to take the logarithm(!) of sqrt(N) to bring it down to the same order of complexity as log2(N).
For example, for a binary number with 11 digits, 0b10000000000 (=210), the square root is 0b100000, but the logarithm is only 10.
Related Posts:
- What does O(log n) mean exactly?
- how to calculate binary search complexity
- What does O(log n) mean exactly?
- Why is the time complexity of both DFS and BFS O( V + E )
- Breadth First Search time complexity analysis
- Time Complexity of the Kruskal Algorithm?
- O(n log n) vs O(n) — practical differences in time complexity
- Best case time complexity for selection sort
- Trie complexity and searching
- Merge sort time and space complexity
- How to calculate time complexity of backtracking algorithm?
- Hash table runtime complexity (insert, search and delete)
- Which is better: O(n log n) or O(n^2)
- Quickselect time complexity explained
- Difference between Big-O and Little-O Notation
- Why is O(n) better than O( nlog(n) )?
- Is there an O(n) integer sorting algorithm?
- In a triangulated isometric grid, what triangle is a given point in?
- How do I check if an array includes a value in JavaScript?
- What is a loop invariant?
- What is a loop invariant?
- When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? [closed]
- What is Sliding Window Algorithm? Examples?
- Quicksort with Python
- What is the difference between tree depth and height?
- how to implement quick sort algorithm in C++
- Python: maximum recursion depth exceeded while calling a Python object
- Understanding Time complexity calculation for Dijkstra Algorithm
- Time complexity of a Priority Queue in C++
- What is stability in sorting algorithms and why is it important?
- Counting the sum of every nodes’ neighbors’ degrees?
- Quick Sort Vs Merge Sort
- Polynomial time and exponential time
- Insertion Sort vs. Selection Sort
- Difference and advantages between dijkstra & A star
- Best Case for Bubble Sort
- How to find the kth smallest element in the union of two sorted arrays?
- When will the worst case of Merge Sort occur?
- Big O, how do you calculate/approximate it?
- Performing Breadth First Search recursively
- Is Quicksort in-place or not?
- longest increasing subsequence(O(nlogn))
- When should I use Kruskal as opposed to Prim (and vice versa)?
- Trying to understand max heapify
- Shortest possible depth of a leaf in decision tree (comparison sorting algorithm)
- Python Weighted Random [duplicate]
- What is the meaning of “exclusive” and “inclusive” when describing number ranges?
- What’s a good algorithm to generate a maze?
- Intuition for perceptron weight update rule
- Easy: Solve T(n)=T(n-1)+n by Iteration Method
- What is tail call optimization?
- PacMan: what kinds of heuristics are mainly used?
- Quicksort vs heapsort
- Big-oh vs big-theta
- Looking for algorithm finding euler path
- What does this definition of contiguous subsequences mean?
- Is log(n!) = Θ(n·log(n))?
- How to find maximum spanning tree?
- Exactly how many comparisons does merge sort make?
- Algorithm to return all combinations of k elements from n
- How to calculate big-theta
- What is the time complexity of while loops?
- Intuitive explanation for why QuickSort is n log n?
- Calculate distance between two latitude-longitude points? (Haversine formula)
- Shuffle a deck of cards in Java
- Median of Medians in Java
- What is a loop invariant?
- What is O(log* N)?
- What is the proper equivalent of “while(true)” in plain C?
- Bellman-Ford vs Dijkstra: Under what circumstances is Bellman-Ford better?
- Asymptotic Notation – does n (log n) (log n) simplify?
- What is the big-O of the function (log n)^k
- How to calculate an angle from three points?
- How to solve: T(n) = T(n/2) + T(n/4) + T(n/8) + (n)
- An example of Best Case Scenario for Quick Sort (Need someone to check if my answer is correct)
- how to write a recurrence relation for a given piece of code
- Why is merge sort worst case run time O (n log n)?
- Why is merge sort worst case run time O (n log n)?
- What is the time and space complexity of a breadth first and depth first tree traversal?
- Create your own MD5 collisions
- A tool for calculating the big-O time complexity of Java code? [closed]
- Image Segmentation using Mean Shift explained
- Finding the median of an unsorted array
- Difference between Big-Theta and Big O notation in simple language
- What is the difference between bucket sort and radix sort?
- How are the following functions O(N^3)?
- Difference between O(n) and O(log(n)) – which is better and what exactly is O(log(n))?
- Finding all possible combinations of numbers to reach a given sum
- Are there any real O(n^n) algorithms?
- Sorting an array in C?
- Is Dijkstra’s algorithm for directed or undirected graphs?
- How to determine if a point is in a 2D triangle?
- Modular multiplicative inverse function in Python
- Minesweeper solving algorithm
- About bubble sort vs merge sort
- Dijkstra’s algorithm in python
- Why doesn’t Dijkstra’s algorithm work for negative weight edges?
- How to replace all occurrences of a character in string?
- What is the difference between a heuristic and an algorithm?
- Running time of algorithm A is at least O(n²) – Why is it meaningless?