Questions tagged [efficiency]

Using as few resources (e.g. time, space) as possible while solving a problem. Use this tag if your question is specifically about resource usage, not for generic algorithm questions that happen to mention running times.

Filter by
Sorted by
Tagged with
-1
votes
1answer
51 views

Finding most efficient sorting algorithm

Arr is an array that contains $ n$ numbers. Suggest the most efficient algorithm for each case and analyze the runtime. Explain why the algorithm you chose is the best one. Arr contains exactly $\...
0
votes
3answers
48 views

Big O Proof , f(n) = 2n + 1 and I have to prove f(n) is O n^2

If I have $f(n) = 2n + 1$ and I have to prove $f(n) \in O(n^2)$, by proving there exists positive constants $c$ and $n_0$ such that $f(n)<cn^2, \forall n\ge n_0$, can I do this all in one step by ...
0
votes
1answer
27 views

How to prove Big-O when $F(N)$ is even or odd

If I'm given a function $f(n)$ which is for example $4n+1$ when even and $3n^2+2$ when odd and I have to prove or disprove $f(n)$ is $\mathcal O( n^2 )$. Do I have to do $f(n) < c n^2$ for all $n &...
-2
votes
2answers
37 views

Calculating efficiency?

A program must construct and then use a set $S$ of 1000 integers. ...
0
votes
1answer
42 views

Efficient algorithm to compare arrays problem

I was submitted an interesting problem, but I wasn't able to find a solution. Define a function p(x, y) that takes int x and y, with ...
1
vote
1answer
25 views

Understanding recursion tree for withdrawal formula

$$ T(n) = T(n-a) + T(a) + cn $$ Now the solution says that the height of the tree $(h)$ is: $$ h = \left \lfloor n/a \right \rfloor $$ And I don't understand why. Maybe I didn't understand the ...
0
votes
1answer
27 views

Why substituting the search part in INSERTION SORT doesnt yield a running time of $\Theta(nlgn)$

$$ \Theta - Tight \ asymptotic \ bound $$ If we change lines $5-7$ in Insertion sort With BINARY-SEARCH(A,p,r,v) Why don't we get a running time of $\Theta(n\lg n)$ as we go through the array $\...
1
vote
2answers
32 views

What's the most time efficient way to find the number of nodes reachable from each root and no other root?

Suppose there are n nodes. These nodes are connected by m unique directed edges. Sets of these edges may form cycles. Each node ...
0
votes
0answers
14 views

Parent Node in BST

Is it a good idea to store a pointer to the parent node in a binary search rather than to find the parent node several times? ...
0
votes
1answer
20 views

Comparing the efficiecy of 2 run times

I have a heap with $n$ elements. $k$ represent a number that is the height of one of the elements in the tree. I need to compare two run times and prove what i claim. The 2 run times are: $$ (1)O(...
0
votes
2answers
28 views

Findind The n/lgn intermidiate values in an unsorted array with asymptotic run time of $\Theta(n)$ SELECT algorithm

Let $A[1..n]$ be an unsorted array, we want to find the $n/lgn$ intermidiate numbers in the array. Namely the $(n/2)+1$ biggest number and the $(n/2) + 2$ biggest number and so on... until the $(n/2)...
0
votes
1answer
20 views

reordering a max heap that the values of one of her subtrees has been changed

Let $H$ be a max binary heap with $n$ elements (vertexes). Pick a vertex $z$ in the heap with height of $k$ ($0<k<\lg n$) To every element in the sub heap of $z$ we add the constant value $c &...
0
votes
2answers
49 views

Heaps and Heapsort - Find the 7'th biggest value in a min heap by $O(1)$

I have a min heap. I need to find the 7'th biggest value in the heap with $O(1)$. I need to build the algorithm. I dont realy have an idea how to get to this efficiency. Help? Thanks.
0
votes
0answers
21 views

What's the best bucket fill algorithm in terms of efficiency? [duplicate]

I am looking for an algorithm that fills a given region of connected particular nodes in minimum time. I have tried using flood flow algorithm but it's too slow and inefficient for large array, it ...
3
votes
1answer
94 views

Dynamic Program to solve an NP-complete partitioning problem

I have this problem for which I am struggling to find an efficient dynamic programming algorithm. Would be thankful for some help!! Let $A = \{ a_1, a_2, ..., a_n \}$ be a set where $a_i \in \mathbb{...
1
vote
1answer
19 views

For $T(n) = 16(T/4) + n^2\lg^3n$ prove: $T(n) = \Theta(n^2\lg^3n)$

Define: $ \lg x = \log_2x $. Let $ f(n), g(n) $ be some non-negative functions. Define $ f(n) = \Theta (g(n)) $ if $$ \exists c_1,c_2 \in R\colon 0 < c_1g(n) \leq f(n) \leq c_2g(n) $$ I want ...
2
votes
2answers
36 views

Does the word “efficient” usually refer to polynomial time or polylogarithmic time?

This question is strictly about terminology. I'm not an expert in CS, but I've almost always seen the word "efficient" applied to an algorithm to mean "of polynomial runtime". E.g. this question and ...
1
vote
0answers
13 views

Regex vs line by line read efficiency - general concept question

Say, I have a file that is somewhere between 10-20 pages long. I need to extract 10-20 pieces of information from it that I can fairly easily extract using a series of regex-es or by running code that ...
0
votes
0answers
29 views

Amdahl's Law and efficient algorithms

Does the efficiency of algorithm leading to better performance of the system can be attributed to Amdahl's Law? or Is the Amdahl's law only applicable for the analysis of efficient hardwares and ...
0
votes
2answers
62 views

To calculate how many times a certain year repeats itself in the calendar within a given year range

Let's say I have a year $Y$. I wanna know how can I calculate the number of times the calendar configuration of the year $Y$ repeats itself in the year range $[A, B]$. Is there any method to it ...
3
votes
1answer
251 views

Add edges to undirected graph to make connected and minimize longest path

I am trying to find an efficient algorithm to solve to following problem: Given an undirected disconnected graph, I want to add as few as possible edges to make to graph connected while minimizing the ...
0
votes
1answer
37 views

Is it true that for every genetic algorithm there exists a non-genetic algorithm that achieves the same results more efficiently?

And if it is not true, what are the problem classes or characteristics for which genetic algorithms are superior?
1
vote
0answers
32 views

Least computationally expensive bitwise addition

I am familiar with the oft-cited method of bitwise addition using XOR and left shift for the carry, applied recursively. I was wondering if this is the least computationally expensive way to achieve ...
3
votes
2answers
207 views

Algorithm for detecting overlaps

This is a real-world application, not a student assignment. Suppose a list of events of that have startTime and endTime, and ...
4
votes
0answers
61 views

Peculiar MCMC sampling problem

I have two random variables, X and Y, and Y is a positive real number. I can sample from $p(y|x)$, but I need to sample from $p(x)$, which I know to be proportional to $\frac 1 {E[y|x]}$. I could ...
0
votes
2answers
77 views

Figuring out when one algorithm will be slower than another algorithm [closed]

I'm studying for a computing exam and came past the following question on a past paper and need help with it. When would algorithm A be slower than algorithm B? Demonstrate your answer with the help ...
1
vote
1answer
297 views

Shortest path in a incomplete graph

I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. ...
-3
votes
2answers
637 views

BigO time complexity of 3 nested for loops

I'm debating with a friend whether a particular function I wrote is $O(N^3)$ or $O(N \times M \times X)$ I believe it is the latter since all 3 variables differ in size. $N = 100, M = 50, X = 10000$ ...
4
votes
1answer
77 views

Calculating all products of $n-1$ factors when given $n$ factors

Let's assume we have an operator $$ \times: E^2\to E$$ of which we merely know that it is associative. Let's say a multiplication $e\times f$ always takes up a time of $M$ for all $e, f\in E$. We're ...
1
vote
1answer
50 views

How much does C# gain from its value types

C# makes an distinction between value types and reference types contrast to Java where all (except primitives types) are of reference semantics. The design decision, as I understand it, is mainly to ...
0
votes
1answer
105 views

In which order to solve subproblems when using memoization?

I am currently trying to solve a task with memoization. I have following recursion: A (i, j) = f( A (i, j-1), A (i-1, j-1), A (i-1, j + 1) ) I am not sure in which order the sub-problems should be ...
3
votes
2answers
179 views

Efficient data structure handling insert(number) and find(sum) returning pair a,b such that a + b = sum

There are two operations as follows: insert(num): insert num into the data structure. find(sum): return a pair(a, b) such that <...
1
vote
1answer
63 views

MergeSort k arbitrary words in linear time

Given $k$ arbitrary words, such as $\{\text{"fjqke"}, \text{"gbqig"}, \text{"a"}\}$, is there a way to mergesort these words in linear time so that the final output would be "abefgggijkq"? I tried to ...
3
votes
1answer
146 views

Efficient algorithm to determine if a lambda calculus term is equivalent to one without a given free variable

Consider the following problem: given a lambda calculus term $t$ and free variable $v$ determine whether $\phi(t,v)$, where $\phi(t,v) := \exists t'. t' \equiv t \land v \notin FV(t')$. This problem ...
1
vote
2answers
62 views

Is there a running hash algorithm that can efficiently handle arbitrary updates to a file's contents?

This question is about file-hashing/fingerprinting algorithms (similar to SHA-1 and MD5 and so on). Those algorithms are handy ...
1
vote
1answer
75 views

“Ways to make change for a dollar”: How to optimize with constraints

I'm working on an algorithm that takes a number of unit coins ([1, 2, 5, 10] for example) and a certain amount of money (13 in this case), and figures out how many ways there are to provide change for ...
3
votes
1answer
204 views

Longest substrings of common length with the same parity

Given two sequences $a$ and $b$, find largest $x$ such that in $a$ there is substring $A$ and substring $B$ in $b$ meeting those conditions: length of both $A$ and $B$ is equal to $x$; sum of ...
0
votes
1answer
258 views

Finding duplicates in a stream of numbers

This is an interview question. Say you have a function foo() which returns some integer. You need to write an algorithm that does the following: (...
1
vote
1answer
55 views

Number of steps in worst Case

we have to run a song on a Walkman,for that we need 2 full batteries.Let s say we have a mixed set of 30 batteries (15 are emtpy and and 15 are full) and then only way to test if the battery full or ...
1
vote
2answers
225 views

Data structure for finding max, inserting and deleting in O(1) and O(n) space

This is an interview question. I need to implement a data structure that supports the following operations: Insertion of an integer in $O(1)$ Deletion of an integer (for example, if we call delete(7),...
12
votes
2answers
282 views

Problems that feel exponential but are P

I'm trying to build a list of algorithms/problems that are "exceptionally useful", as in, solving problems that 'seem' very exponential in nature, but have some particularly clever algorithm that ...
3
votes
1answer
69 views

Why does parallelising slow down this simple problem against looping through all the data?

I've been using multiprocessing and parallelisation for the first time this week on a very large data set using 32 CPUs. I decided to explore it for a smaller task just to see if I could learn ...
1
vote
2answers
44 views

Efficiently find elements which are out of place in an otherwise sorted list

I have some data that includes two columns for dates, and I want to retrieve - based on these two columns - all the instances where an illegal operation has occured. An operation is illegal if the ...
2
votes
1answer
90 views

Linked List in Maximal Scoring Subsequences Algorithm

For a project, I'm implementing the All Maximal Scoring Subsequences algorithm. In the analysis portion of the paper, it describes an optimization that makes the algorithm run in linear time. Namely, ...
-1
votes
2answers
137 views

Will we ever achieve a $O(n)$ general purpose sorting algorithm (or at least better than $O(n\log(n)))$?

I've been thinking about this question ever since I learnt about the $O(n\log(n))$ sorting algorithms such as MergeSort, QuickSort (average case is pretty much worse case with a good choice of a pivot)...
0
votes
1answer
371 views

Is there a more efficient stability index algorithm?

I have this assignment for a class and we're beginning to learn time complexity. I have to find create a Java program that finds the stability indices of an array. Stability index being defined as a[0]...
3
votes
2answers
355 views

How would the use of an external lookup table affect file compression?

It occurred to me that, the way compression essentially works, is that you have a mapping of long patterns to short patterns, which you replace one way to compress and the other to decompress. My ...
2
votes
0answers
1k views

What are efficient data-structures for insert/delete by index?

First of all, a definition of the operations: Insert by index: insert element e at index n, increasing the index of all ...
2
votes
1answer
41 views

Fast computation of k-fibonacci numbers

Let's define the sequence of $k$-Fibonacci numbers as $$ F_i = 2^i, ~~ 0 \leq i \leq k-1 $$ $$ F_i = F_{i-1} + \dots + F_{i-k}, ~~ i \geq k $$ I have a problem which requires to compute $n$-th $k$-...
2
votes
1answer
76 views

Counting restricted partitions

Given positive intgers $N$ and $S$ i need to count in how many ways $N$ can be decomposed as sum of $S$ positive integers not greater than $\frac{N}{2}$: $$ N = x_1 + \dots + x_S, ~~~~ 0 \leq x_i \leq ...

1
2 3 4 5 6