Analyzing an algorithm to determine its time and space performance.
2
votes
3answers
282 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 ...
-2
votes
1answer
42 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
130 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
80 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,...
0
votes
4answers
177 views
How 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
164 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
103 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;
1
vote
0answers
75 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
99 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
654 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
110 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 ...
-2
votes
1answer
165 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
526 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
107 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
101 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
103 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
326 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
307 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
1k 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
733 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 ...
19
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
569 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
254 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
602 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
267 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
3k 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
486 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
140 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 &...
5
votes
1answer
2k views
Compute Adjacent Pair
I was given the following problem:
Integer V lies strictly between integers U and W if U < V < W or if U > V > W.
A non-empty zero-indexed array A consisting of N integers is given.
A ...
2
votes
2answers
1k views
Estimating run time of algorithm
For instance if i have an algorithm that is O(n2) and it will run for 10 seconds for a problem size of 1000. Now if i were to double the problem size to 2000 i want to know the approximate run time in ...
1
vote
2answers
232 views
Algorithm Space and Time Complexity with Consideration for I/O (eg cache)
Is there an expression of performance for an algorithm or data structure that attempts to consider cache and other hardware concerns?
Context: in my class we're looking at binary trees and it seems ...
1
vote
1answer
283 views
Connected components of undirected graph
Suppose I have an undirected graph G with vertices v1...vn and edges. Right now it is in adjacency list representation.
For every time moment I have as input some subset of vertices that are "active" ...
-1
votes
1answer
1k views
worst case comparisons for special case insertion sort [closed]
Consider an Insertion Sort with a Sentinel on n values, where every value occurs exactly
twice in the input (so n must be even).
So the best case input for comparisons is when the elements are ...
0
votes
2answers
156 views
Time complexity analysis for recurrence relation
I was asked to figure out the time complexity analysis for the following recurrence relation
T(n) = 4*T(n-1) + c.
Basically, I did a replacement.. T(n-1) = 4 * T(n-2) + c and so on..
T(n) = 4^k T(1) ...
0
votes
3answers
276 views
Big-O notation for other cases
I was just reading answers to a question Plain English explanation of Big O
From that i came to know that Big-O notation is just an "upper bound" of the complexity of an algorithm?
But can we apply ...
1
vote
2answers
3k views
Lower and Upper bound of an algorithm
I am learning about analysis of algorithms.
I came across the term "upper bound" and "lower bound" in "worst-case" running time of an algorithm.
Are they applicable to only the "worst case" or can ...
0
votes
1answer
583 views
Shortest path to visit all nodes [duplicate]
I am given a set of tourist attractions(nodes identified by x, y) and i need to find the shortest path to visit them.
The way i thought of it, is i will ignore if there are streets available and ...
4
votes
3answers
181 views
Algorithm Analysis: In practice, do coefficients of higher order terms matter?
Consider an^2 + bn + c. I understand that for large n, bn and c become insignificant.
I also understand that for large n, the differences between 2n^2 and n^2 are pretty insignificant compared to the ...
5
votes
3answers
1k views
Loop runtime question
I had an exam today and I feel that I did pretty well, except I could not for the life of me figure out what appears to be an unbelievably simple question.
We were asked to give theta notation run ...
19
votes
5answers
10k views
Algorithms: How do I sum O(n) and O(nlog(n)) together?
I have the follow algorithm which finds duplicates and removes them:
public static int numDuplicatesB(int[] arr) {
Sort.mergesort(arr);
int numDups = 0;
for (int i = 1; i < arr.length; ...
1
vote
2answers
1k views
How to measure algorithm accuracy?
I have a few optimization algorithms (for finding function minimum) and I'd like to check how good they are. Suppose I build test cases and compare the actual results to theoretical ones.
What ...
0
votes
0answers
458 views
Approach for packing 2D shapes while minimizing total enclosing area
Not sure on my tags for this question, but in short ....
I need to solve a problem of packing industrial parts into crates while minimizing total containing area. These parts are motors, or pumps, ...
2
votes
1answer
476 views
Asymptotic running time of for-loops
I have this question which I need answered:
What is the asymptotic running time for the following piece of code?
if (N < 1000)
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)...
1
vote
1answer
351 views
How to approach program design with respect to data strucutres and algorimths - is there an equivelant of the OO design process for d.s.'s + algs? [closed]
My applogies for probably the worst written body of text I have produced in my life and many thanks to those willing to plough through it all.
I was (and still am) not able to clearly express what I ...
2
votes
1answer
129 views
Confusion in understanding the theorem on Amortization
I was reading a book on Algorithm Analysis by Micheal T Goodrich. I came across amortization technique and I got struck in understanding the proof of theorem. I am putting the theorem and the proof ...
1
vote
2answers
2k views
calculate complexity of LinkedHashSet
I have an ArrayList<LinkedHashSet<String>> setOfStrings for example this arraylist internally is composed like:
positionX[hello,car,three,hotel,beach]
positionY[.....]
...
I want to find ...
0
votes
0answers
136 views
Algorithm / working approach to get a random list of data
I am working on a android schedule app but that isn't matter , the problem is a algorithm / methodology so you are welcome to just write the pusedo code to answer.
The data is like this
Place
======...
2
votes
1answer
50 views
What is the order analysis of the following (using a list of primes)
I have the following program:
Iterate x from 1 to N. Check to see if x is prime. If it is, add it to a list of primes.
The way I check to see if it is prime is iterating through the current list ...
1
vote
2answers
498 views
Given two sorted array in ascending order with same length N, calculate the Kth min a[i]+b[j]. Time complexity O(N)
Given two sorted array in ascending order with same length N, calculate the Kth min a[i]+b[j]. Time complexity O(N).
Another variant of the question goes like this:
given a matrix with sorted rows, ...
1
vote
1answer
198 views
How to calculate the worst-case runtime of this search-algorithm
I've written a special indexOf function for a list of unsorted unique values.
I can search for one or multiple (unsorted) values, passed as array/list, and the function will return me an array/list ...
