I have the following question:

Is the following statement true or false?

**All logs to base 2**

log2n is a member of O(log(n))

My attempt:

- log2n - clogn <= 0
- log2 + logn - clogn <= 0
- 1 + logn(1-c) <= 0

Now correct me if I'm wrong, but I have to find values for n (variable) and c (constant) which either prove or disprove this...

Generally this seems to be true:

Choose

```
n0 = 2, c = 3 -> TRUE
n1 = 3, c = 3 -> TRUE
n2 = 4, c = 3 -> TRUE
```

Therefore, the statement seems true, logn increases as n does. But there are also values for which the above statement will never hold:

e.g.

Choose c = 1 evaluates to greater than zero regardless of the increasing value of n.

So I am confused as to whether this is true or false....

You could just use the fact that the logarithm of a product is the sum of the logarithms of the factors:

`log(2n) = log(2)+log(n) = O(log(n))`

Similar Questions

I need help in this question. I really don't understand how to do it. Show, either mathematically or by an example, that if f(n) is O(g(n)), a*f(n) is O(g(n)), for any constant a > 0.

The following code give me a O(n). how do I code a for loop that has time complexity of O(c^k)? int power(int x, unsigned int y) { if( y == 0) return 1; else if (y%2 == 0) return power(x, y/2)*power(x

I had a question about Big O vs little o notation. It seems intuitively, that Big O is like <= while little o is like <. Does that mean that if something is little o of f(n), it is also Big O of

If I have 10 elements and starting with an empty tree, What is the complexity of inserting 10 elements into Red Black in big-O notation? Is it going to be more than O(log 10) because each time it ins

I am attempting to calculate the Big-O of the following algorithm but I am confused and require some assistance: Algorithm 1. DFS(G,n) Input: G- the graph n- the current node 1) Visit(n) 2) Mark(n) 3)

so my data structure class is covering time complexity and I just have a quick question about the performance for arraylist and treemap. The get method for ArrayList is O(1) and the get method for Tre

So I have this problem to do and I am not really sure where to start: Using the definition of Big-O, prove the following: T(n) = 2n + 3 ∈ O(n) T(n) = 5n + 1 ∈ O(n2) T(n) = 4n2 + 2n + 3 ∈ O(n2) if an

To simplify a big O expression We omit all constants We ignore lower powers of n For example: O(n + 5) = O(n) O(n^2 + 6n + 7) = O(n^2) O(6 * n ^ (1/3) + n ^ (1/2) + 7) = O (n^(1/2)) Am I right in

I have noticed that big-O of 1000n or 10n is the same thing as O(n), but big-O of 2^n and 3^n are different: O(2^n) and O(3^n), what I don't get is why can't we ignore the constants in this case (2 or

I missed the class where big-O was introduced thinking that it was pretty straight forward. It still seems to be however the teacher said something about O(n) deviating from the function when n gets v

My question arises from the post Plain English Explanation of Big O. I don't know the exact meaning for logarithmic complexity. I know that I can make a regression between the time and the number of

What is the Big-O time complexity of the following nested loops: for(int i = 0; i < N; i ++) { for(int j = i + 1; j < N; j++) { System.out.println(i = + i + j = + j); } } Would it be O(n

I have a question about the performance of my class project. I have about 5000 game objects formed from reading a text file. I have a Treemap (called supertree) that holds as its nodes Treemaps (mini

What are the space and time complexities, in Big O notation, for the Lempel-Ziv-Welch and Huffman compression algorithms? Google is failing me. Thanks, Francisco

What Big-O notation would this fall under? I know setSearch() and removeAt() are of order O(n) (assume they are either way). I know without the for loop it'd be O(n), for certain, but I get confused h

I am trying to find the Big O for stooge sort. From Wikipedia algorithm stoogesort(array L, i = 0, j = length(L)-1) if L[j] < L[i] then L[i] ↔ L[j] if j - i > 1 then t = (j - i + 1)/3 stoogesort

I'm revising the formal definitions of Big O and the other associated bounds and something is tripping me up. In the book I'm reading (Skiena) Big O is defined as: f(n) = O(g(n)) when there exists a c

I have a really big property list file(approximately 2 MB large) and I need to use the data from it in my application. However, it would not be normal to store all the data in some kind of nsdictionar

I'm examining the function f(n) = N! + 2^N Supposedly, this is O(N^N) I'm not quite sure why this is, or how to prove this is true. I would think that it is O(N!) Can you provide an explanation wh

I have a question regarding time complexity (big O notation) for Java software. Is there a way to quickly calculate or test it (or any website that could calculate it for me would be welcomed). For ex

I am currently watching ocw video courses on Algorithms and in second lecture i stuck at a point where professor proves the following statement by induction:- n=O(1) proof:- For base case 1=O(1) supp

can anyone help me verifying the following complexities: 10^12 = O(1)? 2^(n+3) + log(n) = O(2^n)? f(n) = Omega(n) and f(n) = theta(n) <=> f(n) = O(n) thanks

I have got problem about understanding the following question. It says: Prove that exponential functions have different orders of growth for different values of base. It looks to me like for example

i have a algorithm that opens a textfile, reads between 5 and 20 words, store them into an array and closes the textfile again. Has this algorithm a Big O Natation (1) or (n)?

Based on my understanding, big O is essentially similar to theta notation but can include anything bigger than the given function (e.g. n^3 = O(n^4), n^3 = O(n^5), etc.), and big Omega includes anythi

void bar(int N){ int c=0; for (int i=0; i<N*N; i++) for (int j= i; j< N; j++) c++; } The outer (and inner) loops above never get past N. Would this mean the Big O is N*N (N for the outer and N/

What's the big-O complexity for the following loop: for each vertex u ∈ C do for each vertex v ∈ C and v > u do What I'm doing here is imagine the following set {1,2,3,4} the loop executes a funct

How would you characterize the below in big-O notation? rotors = [1,2,3,4,5 ...] widgets = ['a', 'b', 'c', 'd', 'e' ...] assert len(rotors) == len(widgets) for r in rotors: for w in widgets: ... del w

Good afternoon all, We say that a hashtable has O(1) lookup (provided that we have the key), whereas a linked list has O(1) lookup for the next node (provided that we have a reference to the current n

If I have an algorithm that takes 4n^2 + 7n moves to accomplish, what is it's O? O(4n^2)? O(n^2)? I know that 7n is cut off, but I don't know if I should keep n^2 coefficient or not. Thanks

I may be teaching a Java crash-course soon. While it is probably safe to assume that the audience members will know Big-O notation, it is probably not safe to assume that they will know what the ord

I am trying to calculate the Big-Oh for this code, which is for performing a binary search on a linked list: public int search( List<T> list, T target ) { int low = 0; int high = list.size() - 1

I need to design an algorithm that is able to do some calculations in given O notation. It has been some time since I last calculated with O notation and I am a bit confused on how to add different O

I'm wondering what is the big O notation for each of the below statement: Sum = 0; for i=1 to N^2 do: for j=1 to N do: 'Sum += 1; Sum = 0 is O(1) for sure, because it will only be executed once. But

My textbook is saying that the Big O Notation for finding a Node in a Binary Tree is O(log2N), if N = 1 then log2N would be 0, which is impossible? Would this just be rounded up to 1 or is there more

I am trying to understand how this O notation works and I have below here a block of code, and next to each LINE I will have a comment with the time complexity that I believe it to be. If I am wrong p

while (n >= 1) n /= 2; I am unable to get the Big-O notation for this

I am trying to learn Big-O notation but i have difficulties in calculating time complexity of recursive functions. Can you help me to understand the time complexity of following example? public int r

I've a question regarding big O notation when one is using multiple functions. Lets say I want to find out what the time complexity is for the following pseudo code: heap sort array of size n for i =

Possible Duplicate: What is Big O notation? Do you use it? Hi all, fairly basic scalability notation question. I recently recieved a comment on a post that my python ordered-list implimentation but

Hello I was wondering what would be my Big-Oh for this function: f(n) = 7n – 3nlogn+100000. I checked other similar questions. Some say that since nlogn is -3 we can ignore it and as such the result i

I have a Big O notation question. Say I have a Java program that does the following things: Read an Array of Integers into a HashMap that keeps track of how many occurrences of the Integers exists in

I am working with big multidimensional byte arrays (~500mb per array, like, an array with dimensions of [8,8192,8192]) and I'd like to read and write them into file for storage. I tried using BinaryF

I want to calculate Big O of x++ in below algorithm. for (int i = 2;i < n;i*=2) for(int j = i;j < m;j*=j) x++; I think a lot about it, but I can't solve it. How can I solve it?

If I want to compute the n-th hexadecimal digit of Pi with http://en.wikipedia.org/wiki/Bailey-Borwein-Plouffe_formula what is the big O notation http://en.wikipedia.org/wiki/Big_O_notation for the Ba

So if you use quick sort to sort an array you can do it in O(nlogn) using quicksort and then once you sort it, you can insert new elements into the array in O(logn) with a binary-search-esque algorith

I'm trying to brush up on my big o calculations. If I have function that shifts all of the items to the right of 'i' 2 spaces I have a formula that looks something like: (n -1) + (n - 2) + (n - 3) ..

I have to write down the Big O notation of an algorithm I had to think up for my homework. I'm able to tell that the code below is O(n^2). Because for every x I have to go through all of the y's and

Well I came across this question in one of the books I was referring. I am not quite certain as to what this logically implies. Neither do I have a solution for any deductions. How can we use mathemat

I'm learning programming using YouTube and whatever I can find. I stumbled upon some Big O problems and I'm quite confused on one of them. for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++)