I got asked an interview question that wanted me to discern the Big-O notation of several logarithmic functions. The functions were as follows:

f(x) = log^{5}(x)

f(x) = log(x^{5})

f(x) = log(6*log x)

f(x) = log(log x)

I was told that the Big-O for the first and second are not equivalent and the third and fourth are not equivalent after mistakenly guessing the opposite. Can anyone explain why they are not equivalent and what their Big-O are then?

- log
^{5}x is the same as writing log log log log log x, which is a*very*slow-growing function of x. - This is equivalent to 5 log x (rewriting exponentiation inside the log as multiplication outside), which is equivalent to log x.
- This is equivalent to log 6 + log log x, which is equivalent to log log x.
- This is just log log x.

So you have O(log log log log log x), O(log x), O(log log x) and O(log log x), three distinct Big-O classes.

If your interviewer said 3 and 4 were different, either he was mistaken or you've misremembered the question (happens all the time).

I'll assume you mean `f(n)`

, not `f(x)`

. For 1 and 2, `log^5(n)`

is equivalent to `O(log log log log log(n))`

, while `log(n^5) = 5 log(n) = O(log n)`

.

For 3 and 4, I disagree. `log(6*log n) = log(6) + log(log n) = O(log log n)`

, which is the same as 4 - `O(log log n)`

.

This is a matter of math:

- f(x) = log
^{5}(x) - f(x) = log(x
^{5}) = 5 * log x - f(x) = log(6*log x) = log 6 + log(log x)
- f(x) = log(log x)

So the Big O is

- O(log
^{5}(x)) - O(log x)
- O(log (log x))
- O(log (log x))

So (1) and (2) aren't equivalent, but (3) and (4) are (though they're different from both (1) and (2))

```
f(x) = log^5(n)
f(x) = log(n^5) -> 5 log(n)
O(5 log(n)) < O(log(n)^5)
f(x) = log(6*log n) -> log(6)+log(log(n))
f(x) = log(log n)
log(log n) < log(6) + log(log(n))
```

, although log(6) is a constant so they have same O

Similar Questions

I know that from ECMAScript5 there are two ways of creating objects. 1/ Literal notation which (by default) sets all internal data properties to true (writable, configurable and enumerable. 2/ Using

I like pointer notation in C more than I like array notation, but just can't figure it out for some cases. I have the following code, and the body of main /*converts arguemnt to number using atoi()*/

I have contactid field that is a float with 11 or 12 numbers when I do a insert the numeric number that is the float changes to a scientific notation resulting in a duplicate key error. If I just run

Saw some JS notation today that I've never seen before, bear with me if it is something common that everyone knows. var cookiepath = cookiepath || ''; Now, is this just saying, if a variable named co

Instead of accessing a deep object with a known dot notation, I want to do the opposite: build the dot notation string from the keys of the deep object. So given the following JSON object: { great:{ g

Is there a standard (non-graphical) notation for Entity Relationships? right now I'm using my own janky notation: User >> Photo , (1-many) User > Profile , (1-1 hasOne) Profile < User , (

I am having some trouble working out the Big O notation for these 2 recursive functions: int calc (int n) { if (n <= 0) return 0 ; else if (n > 10) return n ; else return calc (5 + calc(5n)); }

I hear logarithms mentioned quite a lot in the programming context. They seem to be the solution to many problems and yet I can't seem to find a real-world way of making use of them. I've read the Wik

How do I convert scientific notation to regular int For example: 1.23E2 I would like to convert it to 123 Thanks.

I am looking for a javascript library to convert PGN files with move notations including piece and destination like: ... 3. cxd5 Qxd5 ... Into notation only with the square co-ordinates, like: ... 3.

I'm reading a book - Big Nerd Ranch iOS Programming. It says that dot notation is not recommended as it obfuscates code. I am simultaneously watching a Stanford Course for iOS programming and in it he

Possible Duplicate: Plain English explanation of Big O I know Big O notation is used to assess how efficient an algorithm is, but I do not understand how you read Big O notation or what exactly how

if (vector1.x > ((float*)&vector1)[j]) Is j simply just an index into the vector? e.g. is C++ able to retrieve these values using array notation even though vector isn't an array? If so I'm gu

I'm diving into iOS programming and I'm having difficulty getting my head around the idea of Dot Notation and Method Notation. As far as I understand it, Dot Notation can be used to invoke setters/get

What is the difference between Big-O notation (O(n)) and Little-O notation (o(n))?

In a PHP file, I'm trying to convert all array notation into object notation. In other words, I'm trying to convert all occurrences of this: $thing['key'] into: $thing->key I thought this was a sim

i have a Problem with the Xtend Template Notation. I want to do «i=i+1» in a template method def generateSomething() ''' ... «i=i+1» ... ''' The «i=i+1» is obviously only to count i higher but it al

Hi I have built a drum notation system (mostly for hand drums) that allows people to notate drum music. This is done by a form and then they can drag the notes left or right for micro-timing. I have s

Is it possible to force latex to use the slash notation for a fraction (i.e., separating the numerator and denominator with a slash instead of stacking them on top of one another)? Just using a slash

I would like to set up the following custom notation in Mathematica 7. This notation is not particularly useful in itself, so please do not suggest existing alternatives, or point out that this only s

First, here is my code for the O(n): import java.util.*; public class BigO{ public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.print(Enter a number: ); String u

I see this notation, a new operator with a class name and then bracketed code, occasionally in Android examples. Can someone explain this? In the example below, PanChangeListener is a class (or maybe

I am playing around with JS at the moment, coming from Java. I did some Tutorials and need some help with the dot and bracket notation in JS. I made something, I consider an Object in JS. Its called

I have to do some bitwise operations to perform collision checking for my game, but, I've stumbled into some hexadecimal notation I don't know. Example from: http://www.yoyogames.com/tech_blog/7 Usi

I have been learning Objective-C for a couple months. Different books recommend either dot notation or bracket notation. Personally I think, bracket notation looks much cleaner and easier to read. Th

I am actually very beginner in java field and currently going through multithreading concepts I came across a program and had certain doubts regarding the program itself. Following is my program publi

In proving and disproving Big O questions that explicitly say use the definition to prove and disprove, my question is, is what I am doing correct? For example you have a question that is g(n) = O(f(n

I have a SolR query like this: &q=*:*&fq={!geofilt pt=45.15,-93.85 sfield=store d=5} How can I write the same using SolrQuery() object oriented notation from PHP SolR extension API?

I'm parsing .h and .cpp files and I need to find/replace all non-Hungarian notated variables with their Hungarian equivalents. Augh, why?! you ask? My employer requires Hungarian notation, 'nuff sai

Collections vs Arrays regarding sort() What is the difference between these two regarding sort() method? I know Arrays' sort() is using binary search for sort(), what about Collections'? And how to ch

I found this snippet of code in my travels in researching JSON: var array = typeof objArray != 'object' ? JSON.parse(objArray) : objArray; I'm seeing more and more of the ? and : notation. I don't ev

I am trying to solving pythonchallenge problem using Clojure: (java.lang.Math/pow 2 38) I got 2.74877906944E11 However, I need to turn off this scientific notation. I searched clojure docs, still d

Is there a font that can be used for math notation? I'm thinking there isn't. If that is the case, does anyone know what the simplest route is to having nice math notation in my iPad app? Update: Than

I am creating an UML class diagram on Papyrus but I can't understand the notation used for associations. When an association is set to be navigable, the tool adds a black dot on the tip of the arrow a

I am currently working with Reverse Polish Notation. I have able to perform all operation in exception of exponential math. I am aware that C# sharps performs exponential math with Math.Pow but using

I don't find the theory of pointers particularly troublesome, but I am occasionally flummoxed by some of the notation. In the following example, can someone explain how the line p = (int*) a works. Th

I know how to prove algorithms, but I'm not sure how to go about proving exponential and logarithmic ones: Ex: Given f(n) = 1.05^n and g(n) = n^2, determine if f(n)=O(g(n)) Ex: Given f(n) = (log-base4

Ok. So I've been presented with a problem that says there is a bit pattern expressed in hex notation. The first is 0x0C000000 . The thing is, I'm supposed to assume it's a two's complement integer and

How to disable scientific notation in vb6. Ex:if i assign a variable like this a=170000000113123123 It changes to a = 1.70000000113123E+17 After pressing enter.How can we avoid this?

This question already has an answer here: In R, how can I paste 100000 without it being shortened to 1e+05? 2 answers The result of function was displayed in scientific notation, I want to chan

How would I do a left outer join in linq using dot notation? Here's the query expression: var query = from u in db.Users join d in db.Defects on u.userID equals d.userID into defectsGroup from d in de

I've been linting some of my code and got some errors back saying it is better to use dot notation. I found out I was using square bracket notation (with clarity from this great post), however, I want

Coq - IP Notation I want to create a notation for ip addresses. The following is my notation definition that works fine: Inductive IP := ip : nat -> nat -> nat -> nat -> IP. Notation a .

I kind of move between dot notation and bracket notation on the line of code noted below. JavaScript - The Good Parts suggests using dot notation by default. How can I update this code to use the dot

Does anyone know how to make (nice looking) double bracket multiset notation in LaTeX. i.e something like (\binom{n}{k}) where there are two outer brackets instead of 1 as in binomial? You can see an

Polymorphisim in Java stands for many forms what can be achieved by overriding sub-class method. Regarding generics which allows to pass in generic values, such as ArrayList<Object>. Is that par

Can someone explain the star slash notation used throughout magento controllers for redirecting? The use by core code seems to be inconsistent and I cant find any decent docs out there that can explai

I have a very simple grammar to parse statements. Here are examples of the type of statements that need be parsed: a.b.c a.b.c == 88 The issue I am having is that array notation is not matching. Fo

What Big-O notation questions have you been asked? Did you find them to be good questions? Did the interviewer actually understand the concept?

Writing the code below without dot notation, do I have this right? FROM: if(self.yellowViewController.view.superview == nil) { } TO: if([[[self yellowViewController] view] superview] == nil) { } gar