loops,for-loop,time-complexity,nested-loops,asymptotic-complexity , Why does this loop return a value that's O(n log log n) and not O(n log n)?


Why does this loop return a value that's O(n log log n) and not O(n log n)?

Question:

Tag: loops,for-loop,time-complexity,nested-loops,asymptotic-complexity

Consider the following C function:

int fun1 (int n)
{
    int i, j, k, p, q = 0;

    for (i = 1; i<n; ++i)
    {
        p = 0;

        for (j=n; j>1; j=j/2)
            ++p;

        for (k=1; k<p; k=k*2)
            ++q;
    }
    return q;
}

The question is to decide which of the following most closely approximates the return value of the function fun1?

(A) n^3
(B) n (logn)^2
(C) nlogn
(D) nlog(logn)

This was the explanation which was given :

int fun1 (int n)
{
    int i, j, k, p, q = 0;

    // This loop runs T(n) time 

    for (i = 1; i < n; ++i)
    {
        p = 0;

        // This loop runs T(Log Log n) time
        for (j=n; j > 1; j=j/2)
            ++p;

        // This loop runs T(Log Log n) time
        for (k=1; k < p; k=k*2)
            ++q;

    }
    return q;
}

But Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount.

for (int i = 1; i <=n; i *= c) {
    // some O(1) expressions
}

for (int i = n; i > 0; i /= c) {
    // some O(1) expressions
}

But it was mentioned that the inner loops take Θ(Log Log n) time each , can anyone explain me the reason ar is the answer wrong?


Answer:

This question is tricky - there is a difference between what the runtime of the code is and what the return value is.

The first loop's runtime is indeed O(log n), not O(log log n). I've reprinted it here:

p = 0;
for (j=n; j > 1; j=j/2)
  ++p;

On each iteration, the value of j drops by a factor of two. This means that the number of steps required for this loop to terminate is given by the minimum value of k such that n / 2k ≤ 1. Solving, we see that k = O(log2 n).

Notice that each iteration of this loop increases the value of p by one. This means that at the end of the loop, the value of p is Θ(log n). Consequently, this next loop does indeed run in time O(log log n):

for (k=1; k < p; k=k*2) ++q; }

The reason for this is that, using similar reasoning to the previous section, the runtime of this loop is Θ(log p), and since p = Θ(log n), this ends up being Θ(log log n).

However, the question is not asking what the runtime is. It's asking what the return value is. On each iteration, the value of q, which is what's ultimately returned, increases by Θ(log log n) because it's increased once per iteration of a loop that runs in time Θ(log log n). This means that the net value of q is Θ(n log log n). Therefore, although the algorithm runs in time O(n log n), it returns a value that's O(n log log n).

Hope this helps!


Related:


for-loop add columns using SQL in MS Access


sql,ms-access,table,for-loop,iteration
I am trying to add n columns to a table, like in this example of code where n = 10: Sub toto() Dim db As Database, i As Integer Set db = CurrentDb() For i = 1 To i = 10 db.Execute " ALTER TABLE time_series " _ & "ADD...

Javascript: Forloop Difference between i++ and (i+1)


javascript,loops,for-loop
I was building a javascript for loop and I want to compare the value of an array to the next value in the array. If both values are not equal, I want to return true, otherwise I want to return false. In the code below I pass the string "aba",...

Python For Loop Using Math Operators


python,for-loop
Ok, I'm in the process of learning Python, and had a quick question about for loops. I was wondering if you could use math operators in them, like JavaScript. For example, could I do: for i = 0, i < 5, i++: #code here Now, I'm quite aware that Python...

How to match words in 2 list against another string of words without sub-string matching in Python?


python,regex,string,loops,twitter
I have 2 lists with keywords in them: slangNames = [Vikes, Demmies, D, MS Contin] riskNames = [enough, pop, final, stress, trade] i also have a dictionary called overallDict, that contains tweets. The key value pairs are {ID: Tweet text) For eg: {1:"Vikes is not enough for me", 2:"Demmies is...

How can I iterate through nested HTML lists without returning the “youngest” children?


javascript,jquery,html,list,loops
Fiddle: https://jsfiddle.net/zayjeLrk/12/ I want to iterate through an HTML nested list that is 3-layers deep. <ul> <li>animals <ul> <li>birds <ul> <li>crow</li> <li>parrot</li> </ul> </li> <li>reptiles</li> </ul> </li> <li>plants</li> <li>bugs</li> </ul> I want it to iterate through the list so that it returns the elements in this order (note, this isn't...

How are the results for count different in all these three cases?


python,for-loop,while-loop,break
Code 1: iteration = 0 count = 0 while iteration < 5: for letter in "hello, world": count += 1 print "Iteration " + str(iteration) + "; count is: " + str(count) iteration += 1 Code 2: iteration = 0 while iteration < 5: count = 0 for letter in...

Interface Controls for DoEvent in Excel


excel,vba,excel-vba,loops,doevents
I have a macro to loop through a range and return emails to .Display based on the DoEvents element within my module. I iterate that: row_number = 1 'And Do DoEvents row_number = row_number +1 'Then a bunch of formatting requirements Loop Until row_number = 'some value I am wondering...

How to iterate through a table in its exact order?


loops,for-loop,lua,order
If i try to output this table, they are looped through in the false order: local letters = {DIN1="hi", AIN1= "my", AIN2 ="name", DIN2="is"} for name, value in pairs(letters) do print(name,value) end Expected Output: DIN1 hi AIN1 my AIN2 name DIN2 is Output: AIN1 my DIN2 is DIN1 hi AIN2...

How can i make a jQuery animation loop on infinite, after it finish?


jquery,loops,animation
I have a jQuery animation, i have a flying monkey that has to rotate from left to right and from right to left, is working fine but i have to make the monkey loop. Right now i have improvised, i have made several divs into each other that rotate after...

Cancel last line iteration on a file


python,python-3.x,for-loop,file-io
I need to iterate on a file, stop iteration on a condition and then continue parse the file at the same line with another function (That may change so I can't just add content in the previous function). An example file (file.txt) : 1 2 3 4 5 6 7...

for of loop querySelectorAll


javascript,google-chrome,for-loop,mozilla,queryselectorall
Mozilla states that "for of loops will loop over NodeList objects correctly". (source: https://developer.mozilla.org/en-US/docs/Web/API/NodeList) However, this doesn't work in Chrome 43. Is this incorrect documentation or a browser bug? The copied example code used on a page with checkboxes: var list = document.querySelectorAll( 'input[type=checkbox]' ); for (var item of list)...

Get next item in array using iterator using flags


javascript,jquery,loops,iterator,iteration
I am trying to obtain the next object in an object of objects (is you get my drift). I'm looking through the a list of songs, and trying to determine the next song to play. I use the flag playing to check if the song is being played, then i...

Using for loop indices in variable generation SAS


for-loop,sas
I would like to set up a for loop in SAS where I would like to create time dependent tables. The idea is rather simple. I have multiple tables where I would like to left join them and i would like to this operation for every month. I dont have...

How to make function in loop run synchronously?


javascript,jquery,loops,google-chrome-extension,synchronization
Am working on a chrome plugin, and need to sendMessage from an 'app page' to a 'content script' and then get the return messages, from inside a loop. But since the loop doesn't wait for the sendMessage to return a value before starting on the next iteration, it is screwing...

Nested foreach loop in a While loop can make the condition for the while loop go over?


php,loops,foreach,while-loop
Here is a little background on what I am trying to create. I am creating a function called getNextBilling($dateStart,$dateCount = 20) You give it a period length which is the days you want someone to be billed $test->period = '2,5,15'; it takes a starting date which I have assigned on...

Calling function and passing arguments multiple times


python,function,loops
I want to call the function multiple time and use it's returned argument everytime when it's called. For example: def myfunction(first, second, third): return (first+1,second+1,third+1) 1st call: myfunction(1,2,3) 2nd call is going to be pass returned variables: myfunction(2,3,4) and loop it until defined times. How can I do such loop?...

Add mouseListener to Labels in Array Loop


java,loops,mouselistener
I want to add mouseListener to all labels in the array. Every label should show an other card of the layout. If I use below code, all labels show card6. What is wrong? sorry this is correct code.. panList = new JPanel(); panList.setBounds(0, 0, 206, 517); panList.setLayout(null); cs.add(panList); CreateCards(); int...

Why cant I refer to a random index in my 4D list, while I know it exists?


c#,list,for-loop,dimensions
I got a 4D list, and I want where I want to display only the [k][3][j][z], but this isnt working. I checked all the counts and they are all 5+, so 3[4] should work... for (int k = 0; k < lijst4D.Count; k++) { for (int i = 0; i...

Methods within my while Loop not working


python,loops
I'm making a simple script that looks to see if my favourite YouTuber Casey Neistat has uploaded a new video. I want the script to loop over and over so see if there is a new video or not. However, whenever I run the program it continually says that there...

IllegalStateException: Iterator already obtained [duplicate]


java,file,loops,path
This question already has an answer here: java.lang.IllegalStateException: Iterator already obtained 1 answer so I wrote a little Java program to test a little stack language I made vie various test file, but for some reason it won't work. Here is the code: import org.apache.commons.io.FilenameUtils; import java.io.IOException; import java.nio.file.*;...

for each loop: how to step out of conditions


loops,vbscript,condition
I am stuck at creating a loop for testing filenames with VBScript. To be precise, I am trying to perform something like a jump in a For Each loop. The loop should test all files in a folder and in some cases it should delete some files. But while running,...

Appending a data frame with for if and else statements or how do put print in dataframe


r,loops,data.frame,append
How do I put what I printed in a dataframe with a for loop and if else statements? Basically, this code: list<-c("10","20","5") for (j in 1:3){ if (list[j] < 8) print("Greater") else print("Less") }) #[1] "Less" #[1] "Less" #[1] "Greater" Or should it be something more like this? f3 <-...

echo both users


php,mysql,sql,database,loops
The code at the bottom of this post currently echoes: Name: Spongebob Squarepants Description: I live in a pineapple under the sea. Role: editor But there are two users in "wp_usermeta". It's only echoing one. The result needs to look like this: Name: wp_dev_05 Description: My name is Chris Topher!...

Filling PHP array with “for” loop


php,arrays,for-loop,population
I'm trying to populate an array in PHP as following : <?php $maxPages = 20; for ($i = 0; $i <= $maxPages; $i++) { $url = 'http://127.0.0.1/?page='.$i; $targets = array( $url => array( CURLOPT_TIMEOUT => 10 ), ); } print_r($targets); ?> However it only seems to display the last populated...

How to repeat this statement in R probably using apply()


r,loops
It might seem a silly question but how to repeat this line for 152 times and I would not like to use a for loop,since later it will not be efficient with larger data sets: reviews = as.vector(t(mydata)[,1]) mydata is a row in a data.frame and reviews is an array...

An error while looping a linear regression


r,loops,data.frame,regression
I would like to run a loop that will run per each category of one of the variables and produce a prediction per each regression so that the sum of the prediction variable will be deduced from the target variable .Here Is my toy data and code: df <- read.table(text...

How to create series of pandas dataframe by iteration


python,loops,pandas
I want to create df_2008 to df_2014 from an original df by iteration. df has columns names '2008' to '2014' and I want to seperate them into different dfs. I tried for i in range(2008, 2015): 'df_'+str(i)=df[str(i)] Which won't work. I would really appreciate it if anyone could help me....

How to innerHTML a function with array as parameter?


javascript,arrays,loops,foreach,innerhtml
I am learning about looping thorugh arrays - I want to pass the result of an if else statement in the forEach function (inside another function with array as parameter) to HTML using innerHTML (does not have to be innerHTML if you know better methods I do not mind). It...

How to print iterations per second?


python,performance,loops,cmd,progress
I have a small Python script which sends POST requests to a server and gets their response. It iterates 10000 times, and I managed to print the current progress in command prompt using: code=current_requestnumber print('{0}/{1}'.format(str(code),"10000"),end="\r") at the end of each loop. Because this involves interaction with a webserver, I would...

looping variable in swift


swift,for-loop,uiimage
i want to change this variable become looping in swift: var image1 = UIImage(named: "image1") var image2 = UIImage(named: "image2") var image3 = UIImage(named: "image3") var image4 = UIImage(named: "image4") var image5 = UIImage(named: "image5") var image6 = UIImage(named: "image6") var image7 = UIImage(named: "image7") images.append(image1!) images.append(image2!) images.append(image3!) images.append(image4!) images.append(image5!)...

Create a new loop without quotation marks


python,string,for-loop
I wrote a function on python that should print the sentences below. def write_to_file(matrix, path): f = open(path, "w") f.write('\r\n') for i in range (2,5): item = (bestQuarterRate(matrix, i)) item = (str(item)) print item f.write(item) f.close() The problem is that I get this: ('Highest quarter rate is between', '1/1/15', 'and',...

Infinite loop with fread


c,arrays,loops,malloc,fread
I'm trying to allocate an array 64 bytes in size and then loop over the array indexes to put a read a byte each from the inputfile. but when I don't malloc() the array indexes, the loop stays in index0 (so each time it loops it replaces the content in...

How to build a 'for' loop with input$i in R Shiny


r,loops,for-loop,shiny
In my shiny app, I build a a number of checkboxes using a for loop, like this: landelist <- c("Danmark", "Tjekkiet", "Østrig", "Belgien", "Tyskland", "Sverige", "USA", "Norge", "Island") landecheckbox <- c() for (land in landelist){ landechek <- paste0("<label class=\"checkbox inline\"><input id=\"", land, "\" type=\"checkbox\" checked><span>", land, "</span></label>") landecheckbox <- c(landechek,...

Escape out of 2 Javascript loops (or stop script)


javascript,loops
I have a quiz on my site that will submit if the time is up. After the form submits (via jquery), I would like the timer to stop working. I tried putting return: false after the test submits, but that didn't work. html: <span id="time">30:00</span> javascript: var thirtyMinutes = 60...

Creating a number list with nested For loops in Python


python,loops,nested
I've been working on this now for well over four hours and i've tried to check several resources. I'm trying to get something like this: 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4...

performance issues executing list of stored procedures


c#,multithreading,performance,loops
I'm having some performance issues when starting my windows service, the first round my lstSps is long (about 130 stored procedures). Is there anyway to speed this up (except for speeding the stored procedures up)? When the foreach is over and goes over to the second round it goes faster,...

Index out of Range exception in arrays


c#,loops
I am continuously getting out of range exception in my code. I went into the debug mode and found that it was giving an error for the zeroth index itself. Any help would be greatly appreciated. namespace StringTest7 { class Program { static void Main(string[] args) { Input(); StarGenerator(); RemovingWords();...

php for loop of an array


php,html,arrays,for-loop
I have an html form that passes an array into php and then does a for loop to print out values. This is the code that I have $payloads = $_POST['topay']; $loadNum = $_POST['loadnum']; $unit = $_POST['unit']; $driver = $_POST['driver']; for($i=0;$i<count($payloads);$i++) { echo $payloads[$i]; echo "<br>"; echo '<td width="50" valign="top">'.$loadNum[$i].'</td>';...

Java print result every 10th iteration of a for loop


java,for-loop
I'm trying to write simple function to print a message every 5th or 10th iteration of for loop. for example: In this code I want to print i each tenth iteration: private void calc() { int broadcast_by_percent = 100 / 10; int calculate = 0; for (int i = 0;...

Comparing two values in the same row and change if needed


php,mysql,loops
Im trying to compare two values in the same record and if $minvoorraad > $voorraad , set $voorraad = $minvooraad. Database(cropped picture): This is what i have now but it changes all numbers to same <?php session_start(); include 'connect.php'; $sql = "SELECT Minvoorraad, Voorraad FROM product"; $query = mysqli_query($con, $sql);...

Php counting with $i++


php,loops
I have this in a loop: <?php $i = 1; echo '<div id="'.$i.'">' . 'Anchor' . '</div>'; echo '<a href="#'.$i.'">' . 'Link-A ' . '</a>'; echo '<a href="#'.$i.'">' . 'Link-B ' . '</a>'; $i++; ?> This works fine if there is only one object. What do i have to do...

Using Yahoo! database without quantmod functions


r,loops,yahoo-finance
The problem I am trying to solve is looping a string through R with Yahoo! finance api. This would make a bunch of data frame files, but if I could convert it into xts, that would be awesome. However, the xts part is not as important. library(quantmod) DB <- quantmod:::DDB_Yahoo()...

Python - Using a created list as a parameter


python,list,loops,if-statement,compare
When I run my code it tells me: Type Error: unorderable types: str() < float(). I can't figure out why it won't let me compare these two numbers. The list I am using is defined, and the numbers in it have been redefined as floats, so I'm not sure what...

Counter not working after jumps - assembly language


loops,assembly,counter,increment
For some reason, when i switch to mouse input switch back to keyboard input for my program, increasing and decreasing the counter has no effect. It works perfectly in the first loop where we input characters. Here is the program guys, any advice? look at whatspeed jump for reference after...

VHDL average of Array through for loop


arrays,for-loop,vhdl,moving-average
I have an Array of X Integer values in VHDL declared as a variable inside a process. I would like to calculate the average of all Values in a for loop. If I write it out for 3 Values manually everything works fine (tested on hardware): entity MyEntity is Port(...

Run 3 variables at once in a python for loop.


python,loops,variables,csv,for-loop
For loop with multiple variables in python 2.7. Hello, I am not certain how to go about this, I have a function that goes to a site and downloads a .csv file. It saves the .csv file in a particular format: name_uniqueID_dataType.csv. here is the code import requests name =...