Questions tagged [algorithm-analysis]

Analyzing an algorithm to determine its time and space performance.

Filter by
Sorted by
Tagged with
-4
votes
0answers
37 views

Time complexity of closest pair algorithm [on hold]

How is the following expression for the calculation of time complexity correct? 2T(n/2) + O(n) = O(nlogn)
0
votes
1answer
81 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 ...
-2
votes
1answer
24 views

Recurrence of splitting a matrix array? [on hold]

If we have a matrix of nxn, what is the recurrence of splitting it into 4 equal parts of size (n/2)*(n/2)? I thought it would be 4T(n/4) since we are splitting it into a 1/4 of the original size, but ...
2
votes
1answer
231 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 */ ............... ...
-1
votes
1answer
135 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....
1
vote
0answers
41 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 ...
-3
votes
1answer
55 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 ...
3
votes
6answers
623 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, ...
0
votes
1answer
530 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....
1
vote
1answer
626 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 ...
2
votes
1answer
170 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"...
0
votes
1answer
81 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 ...
0
votes
1answer
328 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 ...
6
votes
3answers
2k 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 ...
0
votes
1answer
2k 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 ...
1
vote
1answer
78 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 ...
-1
votes
2answers
162 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}...
2
votes
7answers
500 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 ...
1
vote
2answers
4k 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 ...
-4
votes
1answer
92 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 ...
4
votes
2answers
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 ...
1
vote
3answers
200 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 //...
2
votes
3answers
1k 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 ...
-1
votes
1answer
5k 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....
3
votes
1answer
511 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 ...
-1
votes
2answers
90 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,...
1
vote
4answers
1k 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 ...
0
votes
2answers
1k 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-...
-1
votes
3answers
173 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;
2
votes
0answers
132 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 ...
2
votes
1answer
224 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 ...
2
votes
4answers
2k 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 ...
-2
votes
1answer
189 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 ...
-3
votes
1answer
392 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.
11
votes
2answers
3k views

Time complexity of 2^sqrt(n)

I am solving an algorithm question and my analysis is that it would run on O(2^sqrt(n)). How big is that? Does it equate to O(2^n)? Is it still non-polynomial time?
3
votes
1answer
138 views

Are these graph coloring algorithms equivalent?

Suppose you want to color the vertices of a graph in a greedy fashion, given a predetermined order of these vertices. The goal is to avoid giving two adjacent (linked by an edge) vertices the same ...
1
vote
0answers
248 views

Belman-Ford 2d array variation problem

I've got a problem with applying a Bellman-Ford algorithm to 2D Array (not to graph) Input array has m x n dimensions: s[1,1] s[1,2] ... s[1,n] -> Exit s[2,1] s[2,2] ... s[2,...
2
votes
1answer
628 views

Running time of the specified Bubble Sort Algorithm

I have been working on a few algorithm questions the last few days, and one bubble sort problem in particular has been giving me headaches. for (k=1; k <= A.length - 1; k++) { //Line 1 ...
1
vote
3answers
2k views

What's the big-O complexity of this recursive algorithm?

I am following a course of Algorithms and Data Structures. Today, my professor said the complexity of the following algorithm is 2^n. I waited till the lesson was over, approached him and told him ...
3
votes
2answers
666 views

Big O Nested For Loop Breakdown

I understand how to get a general picture of the big O of a nested loop, but what would be the operations for each loop in a nested for loop? If we have: for(int i=0; i<n; i++) { for(int j=i+...
5
votes
3answers
8k views

Is O(log n) + O(log n) = O(n)? [duplicate]

We know that binary search takes O(log n) in Big O notation but if we need to run twice an algorithm of O(log n), would it be the same as O(n) in time complexity? For example, if I have a method to ...
1
vote
2answers
1k views

Is the time complexity of a while loop with three pointers different than 3 nested for loops?

This program (written in ruby) finds the largest 3 numbers in an array (without sorting the array). It has a while loop with three pointers. My fist instinct, since there is only one loop is to say ...
22
votes
4answers
3k views

When speaking, how can I say that the time complexity order of an algorithm is O(N log N)?

What term can I use to describe something with O(N log N) complexity? For example: O(1): Constant O(log N): Logarithmic O(N): Linear O(N log N): ?????? O(N2): Quadratic O(N3): Cubic
0
votes
3answers
2k views

Best algorithm to determine whether two arrays can be the same in a circular queue

I'm trying to figure out an efficient way to determine whether two distinct arrays of the same size can be shifted to form the same circular queue. For example: Array1 = ['A','B','C','D'] Array2 = ['...
1
vote
2answers
345 views

What is the algorithmic time complexity of this program?

I wrote a simple program in java to create and maintain Dynamic Arrays: public class DynamicArrays { private Integer[] input = new Integer[1]; private Integer length = 0; private Integer ...
1
vote
3answers
2k views

Big O notation of randomness

I was thinking about inefficient algorithms based on randomness and wondered how to categorise them. For instance. Say you wanted to generate all the numbers from 1 to N in a random order but only ...
2
votes
3answers
335 views

Close to knapsack problem?

I think that I am trying to solve a problem somewhat similar to a knapsack problem. I am not sure though. Please see the input given below and my solution. There are three types of items and 4 ...
1
vote
1answer
10k views

Calculate Big-O for nested for loops

I found this nested loop to calculate the Big-O notation. for(i=0;i<n;i++) for(j=0;j<i*i;j++) for(k=0;k<j;k++) I got the time complexity for the algorithm with this polynomial ...
1
vote
3answers
3k views

Check distance between all elements in a list of numbers in O(n*lg(n))

I have an exercise for my algorithms and data structures class, where I basically have to implement a divide and conquer algorithm or function called check_distance to determine whether all numbers in ...
1
vote
1answer
185 views

More efficient alternative that checks if a list can be made a palindrome

For my algorithms and data structures class, I have to write an algorithm that is more efficient in the worst case than the following algorithm: def algo_X(A): i = 0 j = len(A)-1 while i &...