```
int num = n/4;
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
int count = 1;
}
}
}
```

According to the books I have read, this code should be O((n^3)/4). But apparently its not. to find the Big-O for nested loops are you supposed to multiply the bounds? So this one should be num *n *n or n/4 *n *n.

`O((n^3)/4)`

makes no sense in terms of big-O notation since it's meant to measure the complexity as a ratio of the argument. Dividing by 4 has no effect since that changes the value of the ratio but not its nature.

All of these are equivalent:

```
O(n^3)
O(n^3/4)
O(n^3*1e6)
```

Other terms only make sense when they include an `n`

term, such as:

```
O(n^3 / log(n))
O(n^3 * 10^n)
```

As Anthony Kanago rightly points out, it's convention to:

- only keep the term with the highest growth rate for sums:
`O(n^2+n) = O(n^2)`

. - get rid of constants for products:
`O(n^2/4) = O(n^2)`

.

As an aside, I don't always agree with that first rule in all cases. It's a good rule for deciding the maximal growth rate of a function but, for things like algorithm comparison^{(a)} where you can intelligently put a limit on the input parameter, something like `O(n^4+n^3+n^2+n)`

is markedly worse than just `O(n^4)`

.

In that case, *any* term that depends on the input parameter should be included. In fact, even constant terms may be useful there. Compare for example `O(n+1e100)`

against `O(n^2)`

- the latter will outperform the former for quite a while, until `n`

becomes large enough to have an effect on the constatnt term.

^{(a)} There are, of course, those who would say it shouldn't be used in such a way but pragmatism often overcomes dogmatism in the real world :-)

The outer loop is N. The second loop is N/4, and is executed N times, giving N^2/4, or O(N^2).

The last loop is N/4, and is executed N^2/4 times, giving N^3/4.

However, in big-O, it's just O(N^3).

From http://en.wikipedia.org/wiki/Big_O_notation you can see that constants like the 1/4 do not play a role for determining the Big-O notation. The only interesting fact is that it is n^3, thus O(N^3).

A small technicality. Big O notation is intended to describe complexity in terms of the 'size' of the input, not the numeric value. If your input is a number, then the size of the input is the number of digits of your number. Alas, your algorithm is O(2^N^3) with N being the number of digits.

Formally, the time complexity can be deduced like the following:

Similar Questions

I have a two pivot tables constructed from some data (without the same structure), and I need to compare each entry using the Cartesian product of some other tables. I'd like to have some nested for l

Are nested while loops broken in golfscript or do I not know how to use them? I want to iterate Q from 5 to 0, and for each iteration, iterate Z from 10 to 0. The single loops work well separately, an

I've been trying to iterate over a multidimensional array in JavaScript, and print each element in the array. Is there any way to print each element in a multidimensional array without using nested fo

The code below shows nested while loops, but it's not the very efficient. Suppose I wanted to extend the code to include 100 nested while loops. Is there a better way to accomplish this task? <?php

I have some nested models that look something like: class Company has_many :managers end class Manager has_many :employees end class Employee has_many :tasks end class Task end So that's all fine but

I don't understand why, but I'm getting too many inserts and matches generated when I nest these two loops. Any help appreciated! pseudocode two arrays - nested for loops search 2nd array for match of

I have an array to give a set of ranges like range = [[10,15], [7,13], [2,3]..]. I have nested iteration blocks using these ranges like below. (10..15).each{|i| (7..13).each{|j| (2..3).each{|k| puts

Possible Duplicate: How to break out of multiple loops in Python? Is there an easier way to break out of nested loops than throwing an exception? (In Perl, you can give labels to each loop and at le

I am looking for advice about how to parse a single list, using two nested loops, in the fastest way, avoiding doing len(list)^2 comparisons, and avoiding duplicate files in groups. More precisely: I

using nested for loops statements to draw triangles of s. The number of s on the last row is input from the user (valid range: 5 to 21). the out put should look like this: Sample output: How many

I am trying to run 10 instances of a BASH function simultaneously with GNU Parallel The BASH function downloads tiles from an image and stitches them together - first single rows, then each column - t

What is the best way to terminate all nested loops in the example below. Once the if statement is true, I want to terminate the outer for statement (with I). In the other words I need the whole loop t

I am trying to create a nested IF statement to populate a column in my file with either G, S, B or Other but can’t figure out how to when I need to look at data in multiple columns containing multiple

I'm currently implementing an algorithm that constructs a matrix-pattern based on mathematical formulas. To achieve this I use deeply nested for-loops and alot of if-conditions in it. The problem is,

I am trying to vectorize the topological sort for a faster run Part of it is a while with a nested for. I am having trouble with the vectorizing . The idea of thisfunction is tosort interdependent tas

I have a database which has multiple nested associates. Basically, the structure is as follows: Order -> OrderItem -> OrderItemPlaylist -> OrderPlaylistItem -> Track -> Artist I need t

I have a nested list comprehension which has created a list of six lists of ~29,000 items. I'm trying to parse this list of final data, and create six separate dictionaries from it. Right now the code

I have a couple of nested for loops that try to find consecutive and non-consecutive weekdays to print them as a string. Here's a working loop example: week = ['Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat'

I need to make function calls with the values for each variable (wndspeed, xh, yh, A, and B) Does anyone have an idea on how I can do it without using these nested loops? do i=1,windsteps wndspeed =w

I am running into trouble when trying to convert my multiple nested loops into a lambda or linq expression. I think I am having a hard time understanding how to properly access the properties when usi

This part of my code, shown below, is taking long time to run due to many nested loops. Is there a way these nested loops can be obviated to make it run faster? for k = 1:numel(UpscaledZLen.pq) for j

I wish to do something which appear a bit complicated in MySQL. In fact, I wish to open a cursor, do a loop, and in this loop, open a second cursor using the data from the previous fetch to be execute

Thanks for How to use XSLT to convert a XML to Table [CODE UPDATED 11/6], now I am able to convert xml to table by XSLT, however when I add in one more nested loop, the result is not fully loaded, I a

In my application there can be multiple servers to connect to. Each server can have more repositories, that can be opened in the app. I have a few objects for wrapping the logic of calling webservices

never thought i had issues with nested loops well here Iam: What i want to achieve is this: Given two number A and B i need to find all counting numbers between 1 and the A*B for example A=4 B=3 i nee

I've to write a program that get a series of valid inputs from user and then uses the nested loops to draw the inverted triangle. I've managed to work out the triangle but I struggling on inverted tri

I am using a JavaScript function to set a global variable. Below, I have two really dumb example functions. One uses a label to break out of the nested loops. The other uses an empty return. My quest

How can i do that? Let k an integer given for the user, i need dynamically bulid a nested loop of k levels, example: if k = 5, then: int[] a = new int[k]; for(int i=0; i<256; i++){ for(int j=0; j

When I set while1 = false inside of a loop where the value of while1 was true and the loops condition is while(while1) it should exit the loops. In nested if statements it doesn't seem to do this, tho

Is there a way to create multiple model on the same page that are not nested inside another? For instance, I would like to have a form where you can create users. It has two simple fields, firstname a

I am trying a simple nested for loop in python to scan a threshold-ed image to detect the white pixels and store their location. The problem is that although the array it is reading from is only 160*1

I am having trouble finding where jquery is setting the value of autocomplete. I know that it uses a combobox in the background to control what is searchable for the autocomplete. I have been messing

Homework problem for class that involves invoking several for loops, here's the hw problem: Average Temperature Write a program that uses nested loops to collect data and calculate the average tempera

I have a nested for loop that doesn't seem to be working. The inner loops variable is not updating as the outer loop is executing. for line in file: record = line.split(',') id = record[0] mas_list.ap

i am trying to build up a single.php page. this page is used to show a full single post. i have 3 loops on it. first two are used (each) for geting a random post from a specific category. 1 <?php q

Is this code showing nested loops or just a lot of loops after each other? They are all inside of the first loop, but not inside each other. Is this a good practice or not? for (int outputDigits = ST

I've read that one of the key beliefs of Python is that flat > nested. However, if I have several variables counting up, what is the alternative to multiple for loops? My code is for counting grid

I try to understand the new Java 8 Streams and I tried for days to transfer nested foreach loops over collection in Java 8 Streams. Is it possible to refactor the following nested foreach loops includ

Suppose I have the following simple for loops for a simulation and OLS estimation: set.seed (12345) m <- rnorm(20, 0, 1) n <- 10 b1 <- 0.5 b2 <- 2 model1_b <- matrix(nrow=n, ncol=2) mod

I am a newbie in Java and having difficulty in returning a single string from a method that has multiple for loops, each loop iterating 25 times and returning a pass/fail for each iteration. I'm tryin

I am building a restaurant application for which i have created a database which includes name of restaurant.phone number,address,and latitude and longitude.Latitude and longitude is for finding the l

This algorithm looks through a string and tries to find another string. The logic is simple, I guess. Though, I need help finding it's complexity. int find(string mString, string lookUp) { int i, z, j

I have a problem where I have to find multiple combinations of subsets within nested hashsets. Basically I have a master nested HashSet, and from a collection of possible nested HashSets I have to

I tried finding the sum of all numbers of a nested array, but I don't get it to work correctly. This is what I tried: function arraySum(i) { sum=0; for(a=0;a<i.length;a++){ if(typeof i[a]==number

This question already has an answer here: Breaking out of nested loops in Java 20 answers Please have a look at the following code (Java) while((str=br.readLine())!=null) { int tempCounter=0;

I have a Windows Forms (.NET) application that can have multiple documents open simultaneously. It would be convenient to have each document (form) running its own event loop. With brief experimentati

This question already has an answer here: Complexity for nested loops dividing by 2 3 answers I am trying to figure out the complexity of a for loop using Big O notation. I have done this befor

Is there a better way to iterate to my dictionary data without using 3 nested for loops like what I am currently doing given this data below? Btw, i am using python 2.6. data = {'08132012': { 'id01':

Can someone help me with this nested loop? it has the same problem as Loops not working - Strings (Python) but now it is in a csv class that doesn't have a csv.readline() function. import csv import

I have a piece of code that I'm migrating from Fortran to C++, and I'd like to avoid some of the nested for loop structures I had to create in the original F77 code. The problem is this: I have a vec