Compute BigO for a program in Java
I just would like to ask that what is BigO for this program. I think It's n/2
, but I am not sure.
public static boolean isPrime(int k) {
if (k <= 1)
return false;
else if (k > 2 && k%2 == 0)
return false;
else
{
for(int i = 3;i<=k/2;i+=2)
if (k % i == 0)
return false;
}
return true;
}
1 answer

The complexity is
O(k)
which is linear time.Take the worst case execution where
k
is a prime. Then your algorithm will execute all lines until thereturn true;
.Particularly you completely execute the
for
loop which yields(k / 4)  3
iterations:for (int i = 3; i <= k/2; i += 2)
So you get
O((k / 4)  3)
which isO(k)
.
See also questions close to this topic

Java says: **ERROR**: Unable to access javafile
[(It's sad this question has already been asked.)]
I've the batchfile
D:\Hydroper\Projects\Java\ASC\bin\asc.cmd
that executes a JAR file.\target\asc1.jar
in the same directory. Absolute path:D:\Hydroper\Projects\Java\ASC\bin\target\asc1.jar
.However, when I execute my batchfile, I get the Unable to access jarfile error:
asc strict Main.as
but my JAR is there. Even adding a
.jar
or executing with admin privileges the error persists. It was automatically built with Maven.Here my batch:
java jar "D:\Hydroper\Projects\Java\ASC\bin\target\asc1" %*
It works when I do
java jar ... args
manually in the commandline, but I don't like that. I prefer aliasing that command.ClassPath
I've instead also tried something like:
java macromedia.asc.embedding.Main "%*"
It works fine, but ASC doesn't.
asc help
works fine, butasc help Main.as
says my AS file cannot be found, but I'm in the right directory. 
Java Windows Form Application throws error class not founds
I am trying to do CRUD operation by using net beans . I am using windows authentication for connection sql server with java . When i run the application and clicked the submit button its shows following errors .
Class not found Exception
here is code .
private void jButton1ActionPerformed(java.awt.event.ActionEvent evt) { try { Class.forName("com.microsoft.sqlserver.jdbc.SQLServerDriver"); String url="jdbc:sqlserver://KHUNDOKARNIRJOR\\KHUNDOKERNIRJOR;Initial Catalog=3TierInWindowsApplication;Integrated Security=True"; Connection con = DriverManager.getConnection(url); String Query ="Inser into Student (Name,Address,EmailID,Mobile)values (?,?,?,?)"; PreparedStatement pst =con.prepareStatement(Query); pst.setString(1,student_name.getText()); pst.setString(2,address.getText()); pst.setString(3,email_address.getText()); pst.setString(4,mobile_number.getText()); pst.executeUpdate(); JOptionPane.showMessageDialog(null,"Record is inserted "); } catch (Exception ex) { JOptionPane.showMessageDialog(null,"Record is failed to insert "+ex); } }

Partial commit of inheritance entiy when exists a constraint violation
I have mapped three JPA classes, just like this.
@Entity @Inheritance(strategy = InheritanceType.JOINED) @Table(name = "super_table") public abstract class SuperClass { @Id public Integer getId() { return id; } ... } @Entity @Table(name = "child_table_a") @PrimaryKeyJoinColumn(name = "fk_id_super_table") public class ChildA extends SuperClass { ... @Column(name = "serial_code", nullable = true, unique = true) public String getSerialCode() { return serialCode; } ... } @Entity @Table(name = "child_table_b") @PrimaryKeyJoinColumn(name = "fk_id_super_table") public class ChildB extends SuperClass { ... }
So, there is a method to persist objects. This method is annotated by
@Transactional
annotation. My obvious intention is avoid persist something wrong or incompletely.@Transactional(propagation = Propagation.REQUIRED, rollbackFor = Throwable.class) public void salvar(SuperClass obj) { getEntityManager().persist(obj); }
When the object is ok, the method performs right. When the method try to persist an object
ChildA
, if the fields of superclass are ok, but the fieldserialCode
has a value existent on table (unique constraint), the annotated method doesn't throws any exception. When Spring framework tries to commit, it throws an exception (about the data base unique constraint). However the tuple of tablesuper_table
is inserted and committed.Can somebody help me to solve this problem?
I'm using:  Hibernate 4.0.1.Final  Spring 3.2.2  JBoss AS 7.1

How to ignore offset from string datetime
I have been searching to convert string to datetime with ignoring the offset. I have a string with local date time as
20170213T12:11:03.303 +01:00
i want to ignore the offset part and string should be converted to20170213 12:11:03.303
as datetime format. I searched google but could not find one.Referred How to convert string to DateTime in C#?
Not a duplicate of DateTime.ParseExact, Ignore the timezone as while searching didn't know its realted to
DateTimeOffset
.Searched using layman terms and no proper result found. 
How to check difference for data stored in same column in R?
I have a dataset with a column called Person and a column Time. The combination of these columns indicate at which time an employee completed a task. A person can complete multiple tasks on one day. I want to know what the difference between completion of two following tasks from the same person is and I want to store this data in another column. For sure I have to add a new column, but is this doable with one code? Or should I make a column first that stores the time of the next task completed by the same person? Any tips on how to do this?

File transfer time between servers
I have two servers in Digital Ocean and I needed to send file from one server to another. In this case, is it somehow possible to find out how much time it took to transfer the file?

Big O time complexity of n^1.001
 Why is the growth of
n^1.001
greater thann
log n
in Big O notation? Then^0.001
doesn't seem significant...
 Why is the growth of

Which function is faster in terms of time complexity/space python
Suppose we could access yesterday's stock prices as a list, where:
The indices are the time in minutes past trade opening time, which was 9:30am local time. The values are the price in dollars of Apple stock at that time. So if the stock cost $500 at 10:30am, stock_prices_yesterday[60] = 500.
Write an efficient function that takes stock_prices_yesterday and returns the best profit I could have made from 1 purchase and 1 sale of 1 Apple stock yesterday.
The solution I came up with:
def get_best_stock_price(list): first_minimum_value = min(list) index_of_the_minimum_value = list.index(first_lowest_value) new_list_excluding_all_the_unwanted_items = list[new_list_index:] max_new = max(new_list) return max_new  first_minimum_value
The solution they offered:
def get_max_profit(stock_prices_yesterday): if len(stock_prices_yesterday) < 2: raise ValueError('Getting a profit requires at least 2 prices') min_price = stock_prices_yesterday[0] max_profit = stock_prices_yesterday[1]  stock_prices_yesterday[0] for current_time in xrange(1, len(stock_prices_yesterday)): current_price = stock_prices_yesterday[current_time] potential_profit = current_price  min_price max_profit = max(max_profit, potential_profit) min_price = min(min_price, current_price) return max_profit
Is my answer suffice in terms of what they offer? if not how can I improve it. And what is my function lacking?
The function they offer includes O(n) time and O(1)O(1) space in the language of Big O notation.

Big O cost of doing two log(n) operations
As part of a homework assignment, I need to write a method that runs in log n time. However, the only way to write that method is with two operations that run one after the other, each in log(n) time.
I need to swap the minimum value in a heap with a new value. I'm using the following methods in java's Priority Queue poll() add(x)
so if my method executes log(n) and log(n) operations, does that mean it's running in log^2(n) time?
I must be missing something because there's no way to write the method without those two operations.

Complexity analysis of a solution to minimizing concat cost
This is about analyzing the complexity of a solution to a popular interview problem.
Problem
There is a function
concat(str1, str2)
that concatenates two strings. The cost of the function is measured by the lengths of the two input stringslen(str1) + len(str2)
. Implementconcat_all(strs)
that concatenates a list of strings using only theconcat(str1, str2)
function. The goal is to minimize the total concat cost.Warnings
Usually in practice, you would be very cautious about concatenating pairs of strings in a loop. Some good explanations can be found here and here. In reality, I have witnessed a severity1 accident caused by such code. Warnings aside, let's say this is an interview problem. What's really interesting to me is the complexity analysis around the various solutions.
You can pause here if you would like to think about the problem. I am gonna reveal some solutions below.
Solutions
 Naive solution. Loop through the list and concatenate
def concat_all(strs): result = '' for str in strs: result = concat(result, str) return result
 Minheap solution. The idea is to concatenate shorter strings first. Maintain a minheap of the strings based on the length of the strings. Each concatenation concatenates 2 strings off the minheap and the result is pushed back the minheap. Until only one string is left on the heap.
def concat_all(strs): heap = MinHeap(strs, key_func=len) while len(heap) > 1: str1 = heap.pop() str2 = heap.pop() heap.push(concat(str1, str2)) return heap.pop()
 Binary concat. May not be intuitively clear. But another good solution is to recursively split the list by half and concatenate.
def concat_all(strs): if len(strs) == 1: return strs[0] if len(strs) == 2: return concat(strs[0], strs[1]) mid = len(strs) // 2 str1 = concat_all(strs[:mid]) str2 = concat_all(strs[mid:]) return concat(str1, str2)
Complexity
What I am really struggling and asking here is the complexity of the 2nd approach above that uses a minheap.
Let's say the number of strings in the list is
n
and the total number of characters in all the strings ism
. The upper bound for the naive solution isO(mn)
. The binaryconcat has an exact bound oftheta(mlog(n))
. It is the minheap approach that is elusive to me.I am kind of guessing it has an upper bound of
O(mlog(n) + nlog(n))
. The second term,nlog(n)
is associated with maintaining the heap; there aren
concats and each concat updates the heap inlog(n)
. If we only focus on the cost of concatenations and ignore the cost of maintaining the minheap, the overall complexity of the minheap approach can be reduced toO(mlog(n))
. Then minheap is a more optimal approach than binaryconcat cause for the formermlog(n)
is the upper bound while for the latter it is the exact bound.But I can't seem to prove it, or even find a good intuition to support that guessed upper bound. Can the upper bound be even lower than
O(mlog(n))
?  Naive solution. Loop through the list and concatenate

Computational complexity of ndimensional Discrete Fourier Transform?
The computational complexity of ndimensional Fast Fourier Transform was discussed here and (as the former's duplicate) here.
The computational complexity of a 1dimensional Discrete Fourier Transform is
O(N^2)
,N
is the data set size.Could you please tell us what is the computational complexity of the ndimensional Discrete Fourier Transform consisting {N1, N2 ... Nn} points along each dimension?

Calculate timings basing on memory references
I read a book which provides the following code and estimates its execution time.
void quicksort(int[] a, int lo, int hi) { if (hi <= lo) return; int i = lo1, j = hi; int t, v = a[hi]; while (true) { while (a[++i] < v) ; while (v < a[j]) if (j == lo) break; if (i >= j) break; t = a[i]; a[i] = a[j]; a[j] = t; } t = a[i]; a[i] = a[hi]; a[hi] = t; quicksort(a, lo, i1); quicksort(a, i+1, hi); }
Then it tells that on a typical computer, the total running time of quicksort might be expressed with a formula, such as
4C + 11B + 35A:
Where
 A – the number of partitioning stages
 B – the number of exchanges
 C – the number of compares
It provides an example of counting coefficient for C. As i understand, there are the following accesses read/write
I
, readV
,A(I)
.LOOP INC I,1 # increment i CMP V,A(I) # compare v with A(i) BL LOOP # branch if less
To start, we might say that one iteration of this loop might require four time units (one for each memory reference).
I don't understand how 11 comes for an exchange:
t = a[i]; a[i] = a[j]; a[j] = t;
Suppose we don't have any optimizations, then there 7 reads:
i
*2,j
*2,a[i]
,a[j]
,t
and 3 writesa[i]
,a[j]
,t
. Even if count reads fromi
andj
twice that is 10, not 11.Also, i would like to know approximately, how value 35 was obtained.
_{The book is An Introduction to the Analysis of Algorithms by Robert Sedgewick and Philippe Flajolet}