algorithm,matlab,time,big-o,nested-loops , Why are my nested for loops taking so long to compute?

## Question:

Tag: algorithm,matlab,time,big-o,nested-loops

I have a code that generates all of the possible combinations of 4 integers between 0 and 36.

This will be 37^4 numbers = 1874161.

My code is written in MATLAB:

``````i=0;
for a = 0:36
for b= 0:36
for c = 0:36
for d = 0:36
i=i+1;
combination(i,:) = [a,b,c,d];
end
end
end
end
``````

I've tested this with using the number `3` instead of the number `36` and it worked fine.

If there are 1874161 combinations, and with An overly cautions guess of 100 clock cycles to do the additions and write the values, then if I have a 2.3GHz PC, this is:

1874161 * (1/2300000000) * 100 = 0.08148526086

A fraction of a second. But It has been running for about half an hour so far.

I did receive a warning that `combination changes size every loop iteration, consider predefining its size for speed`, but this can't effect it that much can it?

As @horchler suggested you need to preallocate the target array

• this is because your program is not `O(N^4)` without preallocation
• each time you add new line to array it need to be resized
• so new bigger array is created (as matlab do not know how big array it will be it probably increase only by 1 item)
• old array is copied to it
• then deleted
• so when you have 10 items in array and adding 11th
• then a copying of 10 items is added to iteration ...
• if I am not mistaken that leads to something like `O(N^12)` which is massively more huge
• estimated as `(N^4)*(1+2+3+...+N^4)=((N^4)^3)/2`
• also the reallocation process is increasing in size breaching CACHE barriers
• slowing down even more with increasing `i` above each CACHE size barrier

The only solution to this without preallocation is to store the result in linked list

• not sure Matlab has this option
• but that will need one/two pointer per item (32/64 bit value)
• which renders your array `2+` times bigger

If you need even more speed then there are ways (probably not for Matlab):

• use multi-threading for array filling is fully parallelisable
• use memory block copy (`rep movsd`) or DMA the data is periodically repeating
• You can also consider to compute the value from i on the run instead of remember the whole array, depending on the usage it can be faster in some cases...

# Related:

## Should checking loop conditions be counted towards total number of comparisons?

c++,algorithm,sorting,c++11
I have implemented three different sorting algorithms and now I want to confirm that my approach of counting the total number of comparisons is correct. In my mind, the number of comparisons shouldn't be tied to the conditional branches because if the condition isn't met, the comparison was still made...

## Identify that a string could be a datetime object

python,regex,algorithm,python-2.7,datetime
If I knew the format in which a string represents date-time information, then I can easily use datetime.datetime.strptime(s, fmt). However, without knowing the format of the string beforehand, would it be possible to determine whether a given string contains something that could be parsed as a datetime object with the...

## How to force my output data in a inputdlg on Matlab be a double?

matlab,typeconverter
I'm currently using a MATLAB to work and I need some help: I need to convert my output data (variable: units) be a double instead of a cell because I must perform a sum: units = inputdlg(question,title); sum = units + i; I've tried this code also but didn't solve...

## Operating a C++ class from Matlab without mex [closed]

c++,matlab
Is there an alternative way to call a C++ class using MATLAB, and operate its methods on MATLAB variables?

## Reading all the files in sequence in MATLAB

matlab,image-processing
I am trying to read all the images in the folder in MATLAB using this code flst=dir(str_Expfold); But it shows me output like this. which is not the sequence as i want. Can anyone please tell me how can i read all of them in sequence? for giving downmark, please...

## Why can't I calculate CostFunction J

matlab,machine-learning
This is my implementation of CostFunctionJ: function J = CostFunctionJ(X,y,theta) m = size(X,1); predictions = X*theta; sqrErrors =(predictions - y).^2; J = 1/(2*m)* sum(sqrErrors); But when I try to enter the command in MATLAB as: >> X = [1 1; 1 2; 1 3]; >> y = [1; 2; 3];...

## solve symbolic system of equations inside an array

matlab,system,equation
sorry if it already has a answer..i tried other links but it didn't understand i have 2 1*63 array .landa and v. each of their members are syms. and each v member is a function of all landa members.i have already calculated v members and they are all symbolic equations...

## Matlab Distribution Sampling

matlab,distribution,sampling,random-sample
How can I create a vector x in Matlab that has values between 0.8 and 1.2, randomly sampled from a: 1. Uniform 2. Normal distribution? There are a lot of functions dealing with distributions, but I'm having trouble using them properly....

## How to switch Matlab plot tick labels to scientific form?

matlab,plot
I have a semilogarithmic plot which works so far with semilogx. Now I would like to change the tick labels. Now it says 10^8 10^9 ... 10^13, but I would like to see 1e8, 1e9, ... 1e13 on the x-axis. How can I change that? Cheers Manuel...

## Knapsack with unbounded items

algorithm,dynamic-programming,knapsack-problem
I am familiar with the 0-1 knapsack problem and when you are given a certain number of copies from each item but I can figure out how to solve it when you are given infinite copies of each item using dynamic programming. I am trying to solve it by hand...

## How to reduce time to find the n-th place from consecutive digits number for less than 1 second

php,algorithm,digits
I'm following the programming test, and there are questions like this From this consecutive digits: 123456789101112131415161718192021.... For example The 10th digit is 1 The 11th digit is 0 and so on What is the 1,000,000th digit? What is the 1,000,000,000th digit? What is the 1,000,000,000,000th digit? Your solution should run...

## Create mask from bwtraceboundary in Matlab

I'm trying to create a mask (or similar result) in order to erase pieces of a binary image that are not attached to the object surrounded by the boundary. I saw this thread (http://www.mathworks.com/matlabcentral/answers/120579-converting-boundary-to-mask) to do this from bwboundaries, but I'm having trouble making suitable changes to it. My goal...

## Reverse ^ operator for decryption

c,algorithm,security,math,encryption
I'm trying to reverse the following code in order to provide a function which takes the buffer and decrypts it. void crypt_buffer(unsigned char *buffer, size_t size, char *key) { size_t i; int j; j = 0; for(i = 0; i < size; i++) { if(j >= KEY_SIZE) j = 0;...

## Plot multiple functions on one figure

matlab,matlab-figure
I'm struggling to plot multiple functions on one figure. Here is the code that I have: syms t a; a=0.9514; F1=0.5*sqrt(3*t^2); F2=-0.28375*t^2+1.155*a*(t-a)+1; F3=1; E1=diff(F1,t); E2=diff(F2,t); E3=diff(F3,t); I want to plot E1, E2 and E3, each only within a certain range, to make a "composite" line. I've tried plotting with ezplot...

## MATLAB - How to merge figure sections vertically

matlab,plot
I want to display three figures in a figure window. Assuming that I divide 2x2 regions. subplot(2,2,1) ---------+----------- | R1 | R2 | ---------+----------- | R3 | R4 | ---------+----------- I want to show a figure merging R1 and R3 ant other two in R2 and R4 I can display...

## Getting Wrong Answer in “Longest non regular parentheses sub-sequence ”codechef june cook off

algorithm
I attended a programming competition(it has ended now). I don't know why my solution is giving WA, I read the editorial, saw other people solution but unable to find a flaw in my solution. Obviously I am missing somewhere. Please help! Question Link My Solution My approach If the pattern...

## Giving a string variable as a filename in matlab

string,matlab,filenames
I am using the below mentioned code to get the file names of images according to their id's from images_1 text file as strings and use them to read the images from their directory image_count=1; for image_count=1:6 file=fopen('D:\Academics\New folder\CUB_200_2011\images_1.txt','r'); C = textscan(file, '%s'); original_image=imread('D:\Academics\New folder\CUB_200_2011\images\%s','C{1}{2*(image_count)}'); imshow(original_image) end I am able...

## How to access variables in the properties block of a Matlab System Object?

I am working on a simple System Object in Matlab/Simulink. It looks like this : classdef realtime_header_detectorSO < matlab.System & matlab.system.mixin.Propagates % correlateHeader % % This template includes the minimum set of functions required % to define a System object with discrete state. properties Header %nrOfBitsInPreviousStep=0; s=100; d=zeros(1,s); end properties...

## matlab plots as movie with legend

matlab,plot,legend,movie
i have a question regarding legend for movies. This is my code: fig = figure(); for i = 1: 70000 plot(signal1) hold on; plot([i,i],[-5,5]) plot(signal2,'r') hold off; title('\fontsize{14} my data'); legend('signal1','signal2'); axis tight; f(i) = getframe(fig); end The legend shows the same colors for the first two things I plot....

## Determining if a graph has a cycle without using DFS

algorithm,graph,cycle,dfs
I came around one of those questions in my exams: Topologocial sorting using Kahn's Algorithm requires the graph to be DAG (Directed Acyclic Graph). How can we determine if a graph contains no cycles without using DFS/BFS first? I am trying to answer that for too long now and I...

## What is this algorithm mapping coordinates to numbers called?

algorithm,coordinates,coordinate-systems,coordinate
I'm writing a program for visualizing crystals. As a part of the program, I have to generate all different basic points in a lattice structure. For those that aren't familiar with crystallography, you can find the most general cases of these structures here: https://en.wikipedia.org/wiki/Hermann%E2%80%93Mauguin_notation#Lattice_types The problem was that I wanted...

## Connecting two binary objects in matlab

matlab,image-processing
I have a binary matrix containing several binary objects and I want to bridge between them. Actually I have the following picture: And the result has to be like this: Is there any function or a shortcut way, other than loops, for this problem?...

## Matlab — SVM — All Majority Class Predictions with Same Score and AUC = .50

matlab,svm,auc
I'm having a weird problem in training an SVM with an RBF kernel in Matlab. The issue is that, when doing a grid search, using 10-fold cross-validation, for the C and Sigma values I always get AUC values equal to approximately .50 (varying between .48 and .54 depending) -- I...

## Does there exist an algorithm for iterating through all strings that conform to a particular regex?

c#,regex,algorithm
I'm making a script to try and hack into an account whose login password is at least 8 characters long and includes at least 1 number, 1 special character and 1 capital letter. I will use brute force. Is there a compact, elegant and efficient way to iterate through every...

## thicken an object of image to a curve in matlab

matlab,image-processing
I have a labeled matrix containing two objects. How can I thicken an object to a curve? Actually I have the following image: and I want this: Each pixel of the resulting curve is the median of each column. But if you have another idea, it is acceptable, because I...

## Can we add a statement in between MATLAB codes?

matlab
Is it possible to add statements in between the codes. For example: If I have a code like this, r(:,1) = a(:,1) - a(:,2); Then can I write it as, r(:,1) = a(:,1)("this is a constant") - a(:,2)("this is a variable"); ...

## Recursive solution doesn't iterate correctly

ruby,algorithm,search,recursion
I'm working through a toy problem in Ruby: how to produce all possible 10-digit phone numbers where each successive number is adjacent to the last on the keypad. I've represented the adjacent relationships between numbers, and have a recursive function, but my method isn't iterating through the whole solution space....

## Interpolation inside a matrix. Matlab

matlab,matrix
I have a matrix looks like: 0 0 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 1 0 1 0 0 0 1 0 4 0 0 0 0 0 3 0 0 6 0 0 4...

## how to calculate probability for each class for predicate with knn without fitcknn?

matlab
my matlab version is 2012a. when I use fitcknn,has this error: Undefined function 'fitcknn' for input arguments of type 'cell'. how to calculate probability for each class for predicate with knn without fitcknn? after use this code, I want to calculate prob_estimates for each neighbors: knn = ClassificationKNN.fit(trainsample, trainlabel,'NumNeighbors',7); y...

## Understanding Big-Ω (Big-Omega) notation

algorithm,big-o
I was doing some reading on logarithms and the rate of growth of the running time of algorithms. I have, however, a problem understanding the Big-Ω (Big-Omega) notation. I know that we use it for 'asymptotic lower bounds', and that we can express the idea that an algorithm takes at...

## Dynamic programming: how to design algorithm for when there are two factors to consider?

algorithm,optimization,dynamic-programming,frequency
I have the following problem and I only have a slight idea about it: Consider a tape storage problem. Given n files of length l1,...,ln and frequencies with which they are accessed f1,...,fn, where sum of all frequencies is 1 and 0<fi<1. "Optimal" means to minimize the average retrieval time...

## MATLAB Access Classreg

matlab
So, I want to be able to look at (read: copy) MATLAB's NonLinearModel method of printing the regression results to the screen such as this. Nonlinear regression model: y ~ (alpha1 - alpha2*t^0.5) Estimated Coefficients: Estimate SE tStat pValue alpha1 1.0253 0.0082253 124.66 4.8823e-24 alpha2 0.0061783 0.00073277 8.4314 4.4834e-07 Number...

## two dimensional unique values in Matlab

arrays,matlab
I have two vectors, one of them stores the width dimension of a set of images and another one the height of these set of images. I want to use these values as two dimensional vectors [width height] and store them in a matrix. The first line, for instance, keeps...

## 3 X 3 magic square recursively

c++,algorithm,math,recursion
I'm trying to find all possible solutions to the 3X3 magic square. There should be exactly 8 solutions. My code gets them all but there are a lot of repeats. I'm having a hard time tracking the recursive steps to see why I'm getting all the repeats. // This program...

## Find the shortest path sum in a matrix. Is Dijkstra not optimal for this case?

algorithm,go
I am trying to solve the following problem from project euler (please take a look at description and the example in the link, but here is the short explanation). in the matrix, find the minimal path sum from the top left to the bottom right, by moving left, right, up,...

## Animate through multiple 2D Matlab plots

matlab,plot
I have multiple 2D line plots in Matlab (they represent some wave moving through space). Each plot represents the wave at some time t. I want to animate through these plots (i.e. show the first plot for a fraction of a second, then show the next one, and the next,...

## Plotting random signal on circle

matlab,plot,signals,circle
I have some random signal (for example sin signal) with the time scale. t=0:0.1:2*pi y=sin(t) plot(t,y) Now I want to draw this signal on this circle. So the time vector actually becomes an envelope of the circle. Envelope of the circle represents "y = 0" in cartesian coordinate system. Here...

## what does ellipsis mean in a Matlab function's argument list?

matlab
What is the ellipsis for in this Matlab statement? frame = insertObjectAnnotation(frame, 'rectangle', ... bboxes, labels); ...I could not find in their online doc....

## Algorithmic big o order of growth code

algorithm,discrete-mathematics
I'm doing an online course and i'm stuck on this question. I know there are similar questions but they don't help me. What is the order of growth of the worst case running time of the following code fragment as a function of N? int sum = 0; for (int...

## Why black surf from this Matlab command?

matlab,time-frequency
Code tfr = abs ( tfr ); [row_size, column_size] = size(tfr); tfr = tfr(1:round(row_size/2), 1:row_size); surf(tfr); view(2); I get in R2014b of OSX 10.10.3 Yosemite but rotating around shows that the cells should not be black Why is the output black? I wonder if this is a hardware problem or...

## How to normalise polynomial coefficients in a fraction?

matlab,polynomial-math
I have the following code: syms z Gc=1.582*(1-0.3679*z^-1)/(1+.418*z^-1); Ghp=.3679*(z^-1)*(1+.718*z^-1)/((1-z^-1)*(1-.3679*z^-1)); T=(Gc*Ghp)/(1+Gc*Ghp); clipboard('copy', latex(simplifyFraction(T))); Which results in following for T: How can I normalise coefficients? I.e. I want the z2 in denominator and z in numerator to have the coefficient of 1. Is there any function in Matlab to do so?...

## Saving images with more than 8 bits per pixel in matlab

image,matlab,image-processing,computer-vision
I need to save a set of pre-processing images in matlab, resulting in grayscale images. The problem is the fact that these pre-processed images have pixel values higher than 255. If I save them with imwrite() as, for instance, .PNG files, does matlab normalize the values to be in [0,255]...

## xcorr function with impulse response

matlab,filtering,convolution
I'm trying to design a Wiener filter in Matlab for a deconvolution problem but I'm having a lot of problems. I have a gaussian white noise process with a variance of 1.2 and a impulse response which has length two. Its values are g(0) = 5 and g(1) = 4....

## function wait to execute

matlab,events,delay
In Matlab functions can be started at events,but occasionally, like with the resize function, the events are called in rapid order and the function is called many times in succession, which can cause weird behavior and lag. Is there a way to have it listen for the event but only...

## How to solve for matrix in Matlab?

matlab,matrix,least-squares
How can I solve , where and and in the least squares sense in matlab? So I'd like to have the minimizing as output....

## Create string without repeating the same element jn the string (Matlab)

string,matlab
I have a string "FDFACCFFFBDCGGHBBCFGE" . Could anyone help me to generate a new string with the same order but no element inside repeated twice. Thanks ! The expected output should be like this : "FDACBGHE"...

## How to give mathemarical proof or support my answer through reasoning as a general case?

algorithm
You are managing a software project that involves building a computer-assisted instrument for medical surgery. The exact placement of the surgical knife is dependent on a number of different parameters, usually at least 25, sometimes more. Your programmer has developed two algorithms for positioning the cutting tool, and is seeking...

## Matlab - Multiply specific entries by a scalar in multidimensional matrix

matlab,matrix,multidimensional-array,scalar
I'm having problems multiplying specific values within my multidimensional matrix by a scalar. My matrix has the following dimension: size(comDatabe) = 5 10 3 397 10 The third dimension is an x-y-z coordinate frame. Something went wrong and now my y-axis is defined upside down for one subject (#8 out...

## Algorithm for [inclusive/exclusive]_scan in parallel proposal N3554

c++,algorithm,parallel-processing,c++14
Proposal N3554 (A Parallel Algorithms Library) for C++14, proposes (among other things), what seem to be parallel versions of the current std::partial_sum, e.g.: template< class ExecutionPolicy, class InputIterator, class OutputIterator, class BinaryOperation> OutputIterator inclusive_scan( ExecutionPolicy &&exec, InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); With the explanation Effects: For each...

## Disconnect all vertices in a graph - Algorithm

algorithm,graph
I am looking for an algorithm that finds minimal subset of vertices such that by removing this subset (and edges connecting these vertices) from graph all other vertices become unconnected (i.e. the graph won't have any edges). Is there such algorithm? If not: Could you recommend some kind of heuristics...