```
sum = 0;
for (i=0;i<n/2;i++)
for (j=i; j<n/4; j++)
sum++;
```

What is the big O for the above code? I calculated the big O but I'm not sure if it's correct.

This is my answer

the outer loop will run `n/2`

times

the inner loop will run `(n/4 - 1) = ((n-4)/4 )`

```
T(n) = (n/2) * ((n-4)/4 )
= (n^2 -4n + 16)/8
= 1/8 n^2 - 1/2 n +2
```

so the big O is `O(n^2)`

is this correct?

One very simple way of checking the big O of simple for loops that are nested within one another is this: `O(n ^ (number of loops))`

Note that the above technique is valid only if all the limits of the loop are real multiple of n.

In your question the inner loop is n/2 and outer loop is n/4. Both are real multiples of n. So the big O will be: `O(n ^ 2)`

.

Hope this helped.

Yes, in big O computations leading coefficients and subleading terms are dropped.

The **formal definition** is that `f(x)`

is `O(g(x))`

if `f(x) <= M g(x)`

for `x`

beyond some `x0`

and some constant `M`

. In this case, `M = 1/8`

and `x0 = 4`

.

Well it is O(n^2) and if that's all you care(normally that should be) then you are right. But I don't think the constant is 1/8 though.

If you want to be precise I think it should be:

```
n/4 + n/4 -1 + n/4 - 2 + ... 3 + 2 + 1 = n/4 *(n/4 + 1)/2 = n^2/32 + n/8
```

When i is larger than or equal to n/4, the inner loop wouldn't run. So you shouldn't count that part in.

The formal steps, using Sigma Notation, are like the following:

Similar Questions

Is there a master list of the Big-O notation for everything? Data structures, algorithms, operations performed on each, average-case, worst-case, etc.

void function(int N){ for (int i=0; i<N; i++) for (int j= 0; j< i; j++) System.out.println(j) } For this function, how does the Big O depend on the second for loop because of it being j Also

In big-O notation is O((log n)^k) = O(log n), where k is some constant (e.g. the number of logarithmic for loops), true? I was told by my professor that this statement was true, however he said it wil

I understand that this is O(N^2): Loop from i=1 to N Loop from j=1 to N Do something with i,j But what about this? Loop from i=1 to N Loop from j=1 to i Do something with i,j Is it still O(N^2) or O

I was having problem with the following question Consider the following nested loop construct. Categorize its efficiency in terms of the variable n using big-o notation. Suppose the statements repre

Hello I just have a simple question, why is the big O notation of a sorted array O(log N)? It will be a sorted array.

I am having trouble finding out the Big-O notation for this fragment of code. I need to find the notation for both for loops. public static int fragment(int n) { int sum = 0; for (int i = n; i >= 1

I have been given some code to work out big O runtimes on them, could someone tell me if I am on the right track or not? //program1 int i, count = 0, n = 20000; for(i = 0; i < n * n; i++) { count++

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

Could you please explain how I can get the worst-case Big O of this algorithm. I was reading my textbook and I came across a similar algorithm like this one but still don't understand the logic behind

So I am trying to understand the data types and Big O notation of some functions for a BST and Hashing. So first off, how are BSTs and Hashing stored? Are BSTs usually arrays, or are they linked list

I have an algorithm that takes a DAG graph that has n nodes and for every node, it does a binary search on its adjacency nodes. To the best of my knowledge, this would be a O(n log n) algorithm howeve

Possible Duplicate: Plain english explanation of Big O I'd imagine this is probably something taught in classes, but as I a self-taught programmer, I've only seen it rarely. I've gathered it is some

I have the following question: Solve the recurrence relation simplifying the answer using Big 'O' notation: f(0) = 2 f(n) = 6f(n-1)-5, n>0 I know this is a first order inhomogenous recurrence rela

If there are n properties, then is the Big-O of .GetProperties O(n) or are there are processes involved in the reflection that add complexity? Say there is this defined class: public class Reflector {

From my textbook: O-notation and Complexity of Algorithms It is important not to try and make comparisons between algorithms using O-notation. For example, suppose algorithm A1 and A2 both solve the

if T(n) is O(n), then it is also correct to say T(n) is O(n2) ?

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

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

Is 3^n = O(2^n) how about (3/2)^n = O(2^n) ? Can you explain the answers? I got false for the first since, 3^n grows faster then 2^n no matter what constant C you multiply 2^n by. And same for the sec

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

for i := 1 to n do j := 2; while j < i do j := j^4; I'm really confused when it comes to Big-O notation, so I'd like to know if it's O(n log n). That's my gut, but I can't prove it. I know the whi

When i make the following multiplication in PHP: $ret = 1.0 * 0.000000001; i get the result: 1.0E-9 I want to convert this result into the normal decimal notation, how can i do this? sprintf('%f',$re

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

Hey i have a question. say t(n) = O(n log(n)) and u know that this is true. and then your given these statements and told to say whether they must be true or false. t(n) = n^4 and t(n) = O(N^4) The s

I have the following algorithm that determines the greatest common divisor of two numbers x and y. I need to find the big o notation that describes this algorithm and explain why, but I have no idea h

Possible Duplicate: Plain English explanation of Big O I can't find any sufficient help for learn or understand about O-notation, and how learn about time or space complexity. So please suggest me ,

I was given the following code and was told to find the best and worst case running times in big theta notation. def find(a, target): x = 0 y = len(a) while x < y: m = (x+y)/2 if a[m] < target:

I want to know how can I calculate running time in O_notation in C++ programs? Is there any code for that? I have to use this code for showing the running time clock_t start, end; start = clock(); //C

I need help understanding/doing Big O Notation. I understand the purpose of it, I just don't know how to determine the complexity given a piece of code. Determine the Big O notation for each of the

I would just like to prove the following: Show that 1^k + 2^k+...+n^k is O(n^(k+1)) for every positive integer k I am not sure how to go about it. Normally when I am proving a function is big O of ano

I often here people talk about Big O which measures algorithms against each other Does this measure clock cycles or space requirements. If people want to contrast algorithms based on memory usage what

Hello I've tried my best to understand big-theta and now I get the main conception of the proofs for Big-Oh and Big-Omega but i couldn't find and example that is close to my excercise, because i cant

I've come across some code which could definitely be improved, but i'm wondering about the Big-O notation of my improvements. Their original code adds a element to an array, and each time it does this

X=2, y=1 X=3, y=3 X=4, y= 6 X=5, y= 10 X=6, y= 15 X=7, y= 21 X=8, y=28 I know that f(x) = f(x-1) + (x-1) But...is that the correct mathematical function? What would Big O notation be?

I'm confused about how to do big-O analysis for the following problem - find an element from an array of integers. ( an example problem) my solution sort the array using bubble sort ( n^2 ) binary se

I want to implement at least two different solutions to find N-th largest element with O(N*log(N)) average time complexity in Big-O notation, where N is the number of elements in the list ? which sea

What will be the Big O notation for the above complexity? Is it O(n)

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)

Big 0 attempts to answer the question of inefficiency in algorithmic complexity. N+1 describes inefficiency as it relates to database queries in terms of separate queries to populate each item in a co

for (int i=0; i<V-1; i++) { for (int j=i+1; j<V; j++) { if (matrix[i][j]) { from[nextedge]=i; to[nextedge]=j; nextedge++; } } } I am trying to find out the o notation runtime for the if stateme

Can someone please explain to me the purpose of the constant portion of big O notation. I'll try and explain where I am at right now in terms of understanding: Basically you have a function, for examp

The std::queue class is unclear as to the complexity of the size member function. It appears to be based on the data structure implementation used at the time. One would assume that size would be O(C)

My program of sorting values clocks at: 100000 8s 1000000 82s 10000000 811s Is that O(n)?

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?

The method hasTwoTrueValues return true if at least two values in an array of boolean are true. Provide the Big-O running time for all three implementations proposed. // Version 1 public boolean hasTw

I have studied Introduction to Algorithms by CLRS in great details,but one thing is not clear yet. Why is max(m,n)=O(m,n)? Please explain,it would be great help!

Is it possible to obtain a Big O estimate of Math.random()?

This question already has an answer here: Plain English explanation of Big O 21 answers I really can't figure out what Big-O is and how to use it in practice, so i hope someone could give me

I may have the notation wrong. I think this because are not constants ignored in big O notation? I'm pretty new to all this algorithmic analysis stuff. Any help would be greatly appreciated? I'm going