Skip to main content

Questions tagged [algorithm-analysis]

Analyzing an algorithm to determine its time and space performance.

Filter by
Sorted by
Tagged with
2 votes
7 answers
4k views

Why is big O notation an asymptotic notation/analysis?

An asymptote in mathematics represents a value (line) to which the observed function constantly approaches. In other words, as the value of X increases towards infinity, i.e. decreases towards minus ...
dassd's user avatar
  • 147
3 votes
1 answer
302 views

Algorithms: How do I sum O(n) and O(mlog(n)) together?

I'm doing a running time analysis using the aggregate method and I'm a bit confused about what would be the result in this case. I have some intuition in inferring that it would be O(mlog(n)) but I'm ...
neo's user avatar
  • 51
1 vote
1 answer
101 views

Some questions about shortest-path algorithms

I'm trying to understand why anyone would prefer Floyd-Warshal over Dijkstra: Dijkstra gives a correct result, using an understandable system, combined with backtracking. Floyd-Warshal makes an ...
Dominique's user avatar
  • 1,788
1 vote
3 answers
187 views

How can I mix this grid to guarantee it being solvable in X minimum steps?

Note: This question is not about this particular instance of this grid with these exact words, but about any combination of words. I am programming a puzzle game where you have to arrange a grid of ...
Florian Walther's user avatar
0 votes
2 answers
315 views

fastest way to find number of smaller elements to the right of an array

In Daily Coding Problem, Miller&Wu have the following problem : Given an array of integers, return a new array where each element in the new array is number of smaller elements to the right of ...
molyss's user avatar
  • 181
4 votes
1 answer
987 views

What is the most suitable data structure for IPv4 addresses with intersecting ranges?

Mostly in all routers and operating systems the Longest Prefix Match algorithm is used for searching the trie of IPv4 addresses. Packet filters like Iptables don't need some special data structure for ...
red0ct's user avatar
  • 99
0 votes
1 answer
950 views

Counting primitive operations on recursive functions

I'm reading Algorithm Design and Applications, by Michael T. Goodrich and Roberto Tamassia, published by Wiley. They teach the concept of primitive operations and how to count then in a given ...
André Carvalho's user avatar
0 votes
2 answers
1k views

Calculating time complexity of a code snippet

I am trying to calculate the time complexity of the below code snippet def func() { for(i=1; i<=n; i++) { for(j=1; j<=n; j=j+i) { print("hello") } }...
learnToCode's user avatar
5 votes
4 answers
571 views

Processing a 2D matrix - need to speed up my O(n^4) algorithm

I have an n x n matrix which I need to convert into a list sorted by value. Starting with the maximum value cell at (row x1, col y1), I must immediately exclude all cells where (x >= x1, y <= y1)...
Irfan434's user avatar
  • 187
1 vote
2 answers
142 views

Does a microcontroller provide better accuracy for comparing algorithms' run-times?

I have a set of algorithms to choose from based on their execution speed. I know that it is very hard to get an accurate measurement due to the process scheduling, the time that is actually consumed ...
Sapiens's user avatar
  • 141
3 votes
1 answer
373 views

Why the names Omega and Theta in Big Omega and Big Theta?

There was a question asking what the "O" stands for in "Big O", the answer to which seems to be "Ordnung von"/"order of". I wonder what's the origin of the ...
xji's user avatar
  • 791
2 votes
1 answer
566 views

Running time for simple for loops - Big O notation

I am currently doing some exercises with algorithms and I find myself in a huge problem. It seems that everybody understands this type of problem but I have a really hard time figuring it out. For ...
Samed Škulj's user avatar
21 votes
6 answers
5k views

Using a different algorithm depending on the size of the input

I recently finished a course on advanced algorithms, and another on complexity & computability theory, and in the past few days my mind has been somewhat preoccupied by this question. Why don't we ...
cliesens's user avatar
  • 345
4 votes
2 answers
291 views

How can I know when a paper is too hard for me to be able to implement their code and/or understand their math - within a given deadline?

I've been assigned to explore implementing (along with modifications, so understanding it is a must) this algorithm for the 'Redistricting Problem': https://dl.acm.org/doi/pdf/10.1145/3274895.3274979 ....
Samia Zaman's user avatar
1 vote
0 answers
188 views

Rectangle packing / Bin packing with multiple frames

I have multiple rectangular frames, with different fixed heights. The width should be minimized and there is a maximum width. Then there are many different smaller rectangles. These should be packed ...
Wombosvideo's user avatar
2 votes
2 answers
231 views

Time complexity for a small code

I'm trying to find the time complexity for the following code. N= number of elements in array D= a constant: D>1 V= a constant: V>1000 counter=1; //the maximum value of the counter is N/D. ...
Alice's user avatar
  • 37
3 votes
3 answers
2k views

Are there any programs or IDEs that calculate Big-O notation on functions? Is this something that is possible to program into an IDE?

Is there anything that can calculate the Big-O notation of a function? While learning about Big-O, it is implied that it is pretty trivial to do in your head once you know the basic rules, however if ...
Anon's user avatar
  • 3,613
2 votes
1 answer
5k views

Time complexity of a Nested While loop in a for loop

I'm trying to derive the simplified asymptotic running time in Theta() notation for the two nested loops below. For i <-- 1 to n do j <-- 1 while j*j <= i j = j+1 For i <...
Freakup2's user avatar
0 votes
1 answer
136 views

Do I have do use HashTables/Maps/Hashmaps in this algorithm?

I am doing the Ransom Note algorithm in Hackerrank. The thing is I am not using maps and all the tests pass except for three which execution time takes a lot more. (Kotlin language) I have two ...
coroutineDispatcher's user avatar
2 votes
1 answer
2k views

Do we include output space in space complexity?

For example. I have a function which generates an array with random numbers. int[] generateNum(int n) { int[] result = new int[n]; /* Logic to generate random number */ ............... ...
Bhushan Jagtap's user avatar
-1 votes
1 answer
143 views

static, dynamic analysis - what mistakes were made in the code?

A software company develops software packages for commercial animal farming. A special function in C calculates the daily amount of feed for different kind of animals dependent on their bodyweight....
tenepolis's user avatar
  • 285
1 vote
0 answers
62 views

Logfile correlation finder (for j4Log)

I'm currently analyzing a problem in a old "distributed" system, that only occurs sporadically - as the system does not support other means of debugging help I have to rely on the logs (I did not ...
PaulEdison's user avatar
-3 votes
1 answer
193 views

Questions around calculation of time complexity of an algorithm [duplicate]

I am a newbie to algorithms. One thing that i always get confused is about calculation of algorithm runtimes. For example: The following piece of code in Python for i in range(n): #O(?) i*=k ...
Kiran Hegde's user avatar
3 votes
6 answers
815 views

Is it better to write an efficient algorithm or code that is easier to understand?

So I was recently given a coding assignment from a large financial firm, and I thought of two ways to solve the problem. One of the ways involved 1 outer for loop and 1 inner for loop. In this case, ...
Tyler M's user avatar
  • 89
0 votes
1 answer
852 views

Battery level prediction model

I have the idea of develop a model that predicts the battery charge level of my system for now until the following 5 days. The battery is charged using a solar panel. I am writing my code in Python 2....
Andermutu's user avatar
1 vote
1 answer
838 views

How to reason about complexity of Merging k sorted linked lists?

I am trying to understand Big O notation better to be able to reason about it in a much clearer way and therefore, need some feedback on my analysis given below for problem: Merge k-sorted linked ...
Uthman's user avatar
  • 123
2 votes
1 answer
358 views

Algorithm: Binary Search / Tree / Partitioning on unsortable data?

First, this question is not really about binary search as I neither have sorted data, nor any sortable data at all. :-) W.r.t the "unsortable" claim see below; but I think the title term "unsortable"...
Martin Ba's user avatar
  • 7,627
0 votes
1 answer
755 views

Is my reasoning to determine this algorithm's Big-O correct?

Take the following algorithm with two separate sections, and the sections do not influence each other whatsoever (the function is not recursive, as well). void algorithm(int x) { // This section ...
Inertial Ignorance's user avatar
1 vote
1 answer
2k views

Reverse engineering a checksum or CRC

I am trying to reverse engineer a checksum or CRC wherein an 8 bit number* gets converted to a 5 bit number for error checking. I have an incomplete list of data values and checksums, and need to ...
DrWizard's user avatar
6 votes
3 answers
4k views

Effecient algorithm for data deduplication in procedural code

I have written a data cleansing application which, for the most part, works well. It is not designed to handle large volumes of data: nothing more than about half a million rows. So early on in the ...
Bob Tway's user avatar
  • 3,636
1 vote
1 answer
8k views

Why is the optimal choice for a pivot in quicksort algorithm the median element?

Lately i have been taking an course at brilliant.org, i was exploring a lesson on QuickSort algorithm, found a question. Which of the following would provide the optimal pivot selection at each step ...
Sujal Mandal's user avatar
1 vote
1 answer
98 views

Sorting method for music avoiding title and artist repetition

I'm looking for pseudocode suggestions for sorting my mp3 files in a way that avoids title and artist repetition. I listen to crooners - Frank Sinatra, Tony Bennett, Ella Fitzgerald etc. singing old ...
Jigar Mistry's user avatar
-1 votes
2 answers
288 views

Why in Tournament Sorting do we neglect the number of comparisons to find the Minimum?

Here the professor said that, Tournament sort needs (n-1) + 2(n-1)logn comparisons. {Where (n-1) for calculating Maximum or say creating Tournament structure and 2(n-1)logn for other elements to sort}...
Bhaskar's user avatar
  • 47
2 votes
7 answers
539 views

What is wrong with this algorithmic solution of mine that checks whether a given function returns a sorted array when an array is given as input?

An interviewer asked me this question: Given a function f(ar[]) where ar[] is an array of integers, this functions claims to sort ar[] and returns it's sorted version ars[]. Determine if this ...
Sourabh Khandelwal's user avatar
1 vote
2 answers
6k views

Loop invariant of Selection Sort

Selection Sort(A[1,2..n]:array of integers) 1.for i=1 to n-1 2.for j=i+1 to n 3.if A[j]<A[i] 4 swap(A[i],A[j]) I am trying to prove the correctness of this algorithm,I read from my book ...
Joel Separ's user avatar
-4 votes
1 answer
98 views

Calculating Complexity

I am having trouble calculating the complexity of this problem: REVERSE3(A): // Reverse the order of elements in an array // P is an array; assume generating next permutation takes 1 step. for ...
user3026388's user avatar
5 votes
2 answers
1k views

Algorithm to find Minimum bounding rectangle of fixed area [closed]

I have set of spatial points defined by coordinates (x,y) . I want to find the bounding rectangle of given area that maximizes the number of point inside the rectangle. The obtained rectangle should ...
sanket's user avatar
  • 59
1 vote
3 answers
222 views

How bad would be this algorithm that converts a string to a multiple precision number?

I've been developing a C++ library for multiple precision computations (integers/fixed point), assume positive numbers. The class is something like: class Integer { public: //constructor //...
user8469759's user avatar
2 votes
3 answers
2k views

Is the Time complexity of this function o(n) ? Can it be optimized any further?

This is a very simple function to find if a string is composed of unique characters. I believe that this is a O(n) time complexity as it loops once and has a single if condition. Am I correct? Is ...
Pradeepl's user avatar
  • 133
-1 votes
1 answer
13k views

What is the time complexity of permutations?

I want to just say that it's time O(n) and space complexity is O(n!), but I am not certain. Can anyone confirm this or tell me what it is? https://docs.python.org/2/library/itertools.html#itertools....
John's user avatar
  • 11
3 votes
1 answer
547 views

Algorithms comparison and complexity

I want to sole this problem: Write a method to return all valid combinations of n-pairs of parentheses. The method should return an ArrayList of strings, in which each string represents a ...
user72708's user avatar
  • 159
-1 votes
2 answers
115 views

What programming environments can be used to illustrate and benchmark the unoptimized space complexity of an algorithm?

What programming language along with implementation and compiler can I use to study the pure, unoptimized space complexity of an arbitrary algorithm? And what methods can I use to do so? For example,...
Ryan Jarvis's user avatar
2 votes
4 answers
3k views

How does the dividing Step in Merge Sort have Constant Time Complexity?

I am highly confuse while calculating time complexity of Merge Sort Algorithm. Specifically on the Dividing Step. In the dividing step we have to calculate the mid point of "n" i.e. "q = n/2". How ...
Bhaskar's user avatar
  • 47
1 vote
2 answers
3k views

Loop Invariant in Recursive function

When I was reading Introduction to Algorithms (3rd edition, P188), there is an algorithm called Tail-Recursive-QuickSort and we have to prove the correctness of this algorithm. TAIL-RECURSIVE-...
fois's user avatar
  • 111
-1 votes
3 answers
507 views

Time complexity of an algorithm [closed]

What is the complexity of the following loop? for(i=1;i<n;i=2^i) sum+=i;
Anshul Negi's user avatar
3 votes
0 answers
226 views

String Pattern Matching from Lookup Table - Non-Exponential Solution?

Given the problem... Given a String comprising of non-alhpabetical symbols, and a Lookup Table where a subset of those symbols may equate to a single alphabetical character, output all possible ...
Kevin's user avatar
  • 131
2 votes
1 answer
305 views

Optimizing the exponential smoothing of a big array

I have a large set of values (let's say 1M entries) where I need to apply an exponential smoothing algorithm, but only incrementing one value at a time (all others decay to zero). The trivial ...
Laurent Grégoire's user avatar
2 votes
4 answers
3k views

What is Big-O notation for purely functional languages?

Is it still relevant? Instead of var result = new List<int>(); for (var i = 0; i < prev.Count; ++i) { result.Add(prev[i] * 2); } where the result.Add, prev[i], and * 2 instructions are ...
Josh Grosso's user avatar
-2 votes
1 answer
283 views

Unable to Solve Dynamic Programming

I had an assignment on dynamic programming due last night, but I had to turn it in unfinished because i could not understand how to solve the last problem: The state wants to monitor traffic on a ...
WoernerBro's user avatar
-3 votes
1 answer
704 views

How to find complexity of T(n) = 8T(n/2)+n^2.93(log n)^93?

I believe we have to use a variant of master theorem...can someone suggest me how to find complexity of such equation which doesn't directly fit into Masters theorem.
kranthi kumar's user avatar