I can't solve a problem; can someone help me?

What is the Big O notation for the below statement:-

```
for (int i=2;i<=n;i=i*4)
sum++;
```

Once i grows exponentially, it is O(log(n)).

If n is 16 times larger, it is expected to run the loop only two more times than it would.

Once you know that the starting point and multiplier for `i`

are > 1, their exact values make no difference in big-O terms (they only translate into constants added to or multiplying the core component, `O(log N)`

, and such constants are neglected in big-O reasoning -- that's the **core** point of big-O reasoning, after all!!!).

Try counting the number of loops for a few (small) values of n, then graphing the result (n on horizontal axis, loop count on vertical axis). Playing around with a problem is great when you're first learning.

Depending on which values you pick for n, you may not see the pattern. For instance, the loop count is the same for n=10 and n=20. Considering when the loop count will change will also reveal a pattern which can tell you the big-O timing.

Once you have a better understanding of algorithm timing, you won't need to go through this somewhat time-consuming procedure. You'll be able to figure out the big-O timing algebraically through code analysis.

The way I think of big O notation is how long does it take to complete, which is complexity. For example if you have a bubble sort, as you go to items to be sorted it take approximately n*n operations to complete, which is O(N^2).

For binary search, as you increase n in size, you have log2(n) operations to find the value. Since the number of operation is in terms of log then O(log N) for binary search (where log is log of 2).

For what you have, has increase you have N number of operations (this is even if you offsetting) as it is increasing in a linear fashion, which is O(N). This is the notation for linear search as it may take n/2 options an average to find a value, it is still O(N).

I would look at Wikipedia on O(N) notation. It has a more technical explanation, and more big O notation information.

Since you are doing this as a homework exercise, what you really need to do is go back to first principles; i.e. the mathematical definition of O notation. Work out how many simple computation steps there are as 'n' increases, work out the limit algebraically, and then proceed to the answer.

In practice, most folks estimate the 'O' complexity, based on knowledge of classical examples and a experience. And quite often they get it wrong.

Assuming that "sum++" is constant which is a pretty reasonable assumption the algorithm is O(log_{4} n).

Because the loop goes from 2 to n, you know it is at most O(n). However, because your incremented is multiplied by 4 every loop, there is exponentially less time spent in the loop.

The first 4 values of i are 2, 8, 32, 128 so the formula that shows how many iterations that loops will go through is:

((log(n)/log(2))/2)+0.5

Similar Questions

I'm trying to figure out where O(sqrt(n)) and O(n2 log n) fit in this growth hierarchy listed below. This chapter is so confusing and i'm lost on how to figure this out. Any suggestions would be much

I'm trying to help a friend analyze the complexity of his algorithm but my understanding of Big-O notation is quite limited. The code goes like this: int SAMPLES = 2000; int K_SAMPLES = 5000; int i =

Does an algorithm exist that finds the maximum of an unsorted array in O(log n) time?

How to prove this: 4n = O(8n) 8n = O(4n)? So what are the C and n0 values for both cases?

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

Problem What is this algorithm doing? What does 0x01 represent? What does it mean that m = m >> 1 within the inner while loop? What is this algorithm big-O of? while(n>0) { m = n; while(m) {

I am using a simple example off the top of my head here function factorial(n) if n==1 return 1 else return n*factorial(n-1) function factorial(n) result = 1 for i = 1 to n result *= n return result O

Is O(5n) = 5*O(n) ? From what I understand , O(5n) == O(n). Thus they are not equal? Please correct me if I am wrong.

I am learning algorithm analysis. While doing the theory I across many big-O proofs. I was able to solve them but I need help with omega which is the oposite of big-O? Is 22n = O(2n)? --->My answer

Using an ADT Linked List and the following code, how would I express the runtime in Big O Notation?: def reverse (self): (1)if self._head is not None: (2)temp = self._head.item (3)self._head = self._h

i am trying to find limitations of o notations, i was wondering if there was a simple example that demonstrates an enahncement to a task, where version 1 is the same o notation as version 2, yet versi

I'm relatively new to the practice of determining algorithm runtimes using big-O notation and I have a question regarding the runtime of a sorting algorithm. Let's say I have a set of pairs (a, b) in

What is the Big-O for SQL select, for a table with n rows and for which I want to return m result? And What is the Big-O for an Update, or delete, or Create operation? I am talking about mysql and sql

Is big-O notation a tool to do best, worst, & average case analysis of an algorithm? Or is big-O only for worst case analysis, since it is an upper bounding function?

I'm studying asymptotic notations from the book and I can't understand what the author means. I know that if f(n) = Θ(n^2) then f(n) = O(n^2). However, I understand from the author's words that for in

I have difficulty understand the O(1) notation in this formula, does it stand for a constant? Why would people use big-O notation like this? This formula comes from the paper Balanced Allocations b

I am working on some revision at the moment and specifically going over Big-O notation. I have asked a similar question (which dealt with a different algorithm) but am still unsure if I am going the r

I'm having an issue solving for big theta notation. I understand that big O notation denotes the worst case and upperbound while Omega notation denotes the best case and lower bound. If I'm given an

I'm new to big O notation and have a couple of questions about it in my program. I have a program that has 2 maps. Before adding to one of the maps I loop through each character and randomly change th

def foo(x): if x > 5: return foo(x–1) – foo(x-1) else: return 11 def bar(a,b): if (b > 0): return bar( bar(a, b+1) , b-1 ) else: return 0 How do I find the running time in Big O notation and ho

This question already has an answer here: Is Big O(logn) log base e? 6 answers When articles/question state that the Big O running time of the algorithm is O(LogN) . For example Quicksort has a

How to prove log(n) is big-o of (sqrt(n))? How do I find the c and the n0? I understand to start, I need to find something that log(n) is smaller to, but I m having a hard time coming up with the ex

This isn't actually homework, but I need to understand these concepts in the class. What is the worst-case Big-O performance for the insert, find and remove operations in a general tree? Why is this

For the below function, I did But I must have did wrong ... answer should be O(log n). I am terrible at Big O ... havent fully understood master theorem which is not taught in school yet. They tau

I am currently trying to work out what are the main quantitative differences between a quadratic algorithm, a cubic algorithm and one which is exponential. What I don't understand is what it means by

What is the Big O for the zig-zag merge join algorithm? GAE's Big Table uses it, they go into it in these videos: http://www.youtube.com/watch?v=AgaL6NGpkB8 http://www.bestechvideos.com/tag/zigzag-me

I working on a problem for which I came up with two algorithms: one takes O(n lgn) time but requires extra space and other takes O(n+nlgn) time. So just wanted to ask is O(n lgn) time complexity an im

I am trying to find the big O bound for the following recurrence relation: T(n) = T(n-1) + n^c, where c >= 1 is a constant So I've decided to solve this by using iteration: T(n) = T(n-1) + n^c T(n

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

What is the running time of this algorithm: for i=1 to n^2 for j=1 to i // some constant time operation I want to say O(n^4) but I can't be certain. How do you figure this out?

I have run across this method in our code base and wonder what the Big O is. The method takes a flat list and creates a tree, assigning the Parent and Children values as it goes. private void AddChild

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

show that n2/log(n) + 105×n×log(n5)) = O(n2/log(n)) I am having a hard time solving this. If someone could explain to me why that is true, that would be fantastic.

I've read the topic: Big O, how do you calculate/approximate it? And am not sure what the Big-O notation for the following function would be: static int build_nspaces_pattern(const char * const value,

Below method getValue parses a String, builds a Map based on the String and returns a value associated with the key. Is performance of method below getValue O(n) squared ? I'm basing this on becau

I'm just learning about Big O notation, and I've been going through a few thought puzzles, and I just thought I'd verify with people whether I'm thinking through things correctly. In Javascript would

So I have a quick question on how to verify the big O of a function. for example: a quicksort algorithm sorting an array of 5000000 element yields a time interval of 0.008524 seconds, running the same

I'm trying to find the Big O running time for the following code snippet: for( i = 0; i < n * n; i++ ) for( j = 0; j < i; j++ ) k++; I'm not sure if it would be O(n^3) because of the multiplica

I am currently completing a dissertation concerning the encryption of data through a variety of cryptographic algorithms. I have spent much time reading journals and papers but as yet have been unable

I saw the same question 3 times on Stack Overflow: Complexity of an algorithm Time complexity for two pieces of code Tricky Big-O complexity I wanted to ask the question in one of them but I couldn't

I know that the big-o complexity of the following equation is O(n^3) 4n^3 + 6n + 6 because the n^3 is the dominant term. Would the big-o complexity be the same for the same function, but with a nega

void printScientificNotation(double value, int powerOfTen) { if (value >= 1.0 && value < 10.0) { System.out.println(value + x 10^ + powerOfTen); } else if (value < 1.0) { printScie

I've been having some problems trying to grasp the concept of big O notation. So, by definition big O is as follows, T(n) ∈ O(G(n)) if T(n) <= G(n) * C. Since the the constant C can be any integ

Hello it has been some time sins i have used Big O notation, so i'm a bit rusty. I know that having 1 loop, that loops n times is O(n), and having 1 loop that loops n time within another loop that loo

Suppose there are multiple functions with certain big o notations, anything O(N), O(N^2), etc. If you have a code fragment such as. f1(x); f2(x); f3(x); Are all the big O notations added together or

I am working on solving this problem: Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm. The program produces v.d and v.π for each vertex v in V. Give an O.(V + E)-

i m calculating running time for this algorithm? Cost No Of Times for(j=1;j<=n-1;j++){ c1 n(loop will run for n-1 times +1 for failed cond for(i=0;i<=n-2;i++){ c2 n*(n-1) (n-1 from outer loop

I am doing the exercise of Skiena's book on algorithms and I am stuck in this question: I need to calculate the big O of the following algorithm: function mystery() r=0 for i=1 to n-1 do for j=i+1 to

I need an algorithm which will compute below multiplication of array elements in O(n) arithmetic operations. Let a1, a2, a3...an be sequence of integers. Need an algorithm to compute ∑_(1≤i< j≤n) a

Maybe I'm mistaken in my understanding of Big-O notation (it has been a while since I've taken a course on algorithms) but the following has never made too much sense to me: This would be considered O