I'm trying to determine whether it is: O(1). How can I prove it? In complexity terms, log_b(n) is log(n). So is O(log_2(n)-log_3(n))=O(0)=O(1)? that doesn't seem like a strong proof. Also, this doesn't converge asymptotically, so how can it be O(1)?
What is the asymptotic complexity of log_2(n)-log_3(n)?
276 Views Asked by Binary At
2
There are 2 best solutions below
1
Mare Infinitus
On
Also, you might have a look at Wolfram Alpha
It gives some nice plots for log_2(n)-log_3(n)
And, even more important for you, it describes O(log_2(n)-log_3(n))
Related Questions in COMPLEXITY-THEORY
- Sorting complexity
- Determinating Complexity time
- Probability mass of summing two discrete random variables, in linearithmic time
- A little help finding the complexity of time and and complexity of space
- Most efficient way to print differences of two arrays?
- Calculating the Recurrence Relation T(n)=T(n / log n) + Θ(1)
- How can I tell how many times these nested statements will execute?
- Complexity of this greedy algorithm to find the maximum independent set of a graph
- What is the complexity of this piece of code
- Ways to measure bit sequence complexity
- What is an Approximation Factor?
- Data structure request: Lazily infinite set
- What does it mean that a tree's height is O(lg n)?
- Two functions are not taking the time I would expect due to their big-O complexity, can anyone explain why?
- Booking System is NP Complete
Related Questions in TIME-COMPLEXITY
- Time complexity of the algorithm?
- Shell Vs. Hibbard time complexity comparison
- Time complexity of swapping elements in a python list
- constant time complexity: O(x^c)
- Java TreeMap time complexity - lowerKey
- Complexity of LSD string sort (cfr. Algorithms by Sedgewick & Wayne)
- How to search a unknown composite key for dictionary in O(1) in c#
- Confusion about why NP is contained in PSPACE, EXPTIME etc
- Depth first search or backtrack recursion for finding all possible combination of letters in a crossword puzzle/boggle board?
- Time complexity of nested for loops
- TIme complexity of various nested for loops
- Best case performance of quicksort (tilde notation)
- Ranking a given list of integers in less than O(n^2)
- Bellman-Ford algorithm proof of correctness
- Division of very large numbers
Related Questions in ASYMPTOTIC-COMPLEXITY
- TIme complexity of various nested for loops
- Time complexity of if-else statements in a for loop
- Why does this loop return a value that's O(n log log n) and not O(n log n)?
- Asymptotic complexity for typical expressions
- Have I properly sorted these runtimes in order of growth?
- Asymptotic complexity of binary heaps implemented with sets vs. priority queues
- Complexity of for loop
- Complexity of these two nested for loops
- Overall Big-O complexity of a while loop, with inner step that increases with every loop
- Asymptotic time complexity of recursive function (Theta)
- Theta time complexity for loop
- How can I implement a collection with O(1) indexing and mutability in Haskell?
- Time Complexity of the Kruskal Algorithm?
- building/inserting into sorted list
- Asymptotic run time complexity of an expression
Related Questions in COMPUTER-SCIENCE-THEORY
- Designing a DFA (alphabet 'a' and 'b') : The number of 'a' in the string must be a multiple of 3, and the string does not contain 'aba'
- What is the asymptotic complexity of log_2(n)-log_3(n)?
- Why are all the fundamental data structures in computer science recursive in nature?
- Proof by induction binary tree of height n has 2^(n+1)-1 nodes
- How to covert bnf to ebnf from that !? bnf <Z> ::= DCd | D<N>C
- how to prove {(a^m)(b^n)(c^k): m!=k and m,n,k ∈ N} is non-regular?
- Is there any algorithm for converting the 2d images into 3d model?
- Pumping lemma for CFL
- LISP 1.5 How lisp is like a machine language?
- Choosing the optimal radix/number-of-buckets when sorting n-bit integers using radix sort
- How can I find the impact factor of a publication in IEEE library?
- Is the execution of kernel code for handling a system call from a process considered part of the process?
- Comparison sorting algorithms evaluating more than 2x elements at each step
- the stack size in a PDA M can grow to hold at most k symbols. What kind of language is L(M)?
- CPU organization
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
...your proof is wrong. O(log_2(n)-log_3(n))==O(log(n)/log(2)-log(n)/log(3))==O(log(n)*(1/log(2)-1/log(3))=O(Clog(n))=O(log(n)).