The Big-O notation is used to represent asymptotic upper bounds. It describes relevant time or space complexity of algorithms. Big-O analysis provides a coarse and simplified estimate of a problem difficulty.

learn more… | top users | synonyms

0
votes
1answer
44 views

How should I express the complexity of two nested loops over different datasets in Big O notation?

I'm more or less teaching myself big O notation, so please forgive me if this is a duplicate of a question which applied to my question without me having the wisdom to realise it. For my own ...
0
votes
2answers
59 views

Big O Notation of an example

My professor gave this example in a lecture: Example: Given an integer N, print out the values 1…N. for (int i=1; i<=N; i=i+1) { System.out.print(i); } The professor said that the loop ...
0
votes
0answers
88 views

Java Multi-threading

I was solving this question in Java where the user enters a partitioned array. The computer then determines what all elements from that array can be used as pivots. (Pivots are the same pivots that ...
4
votes
3answers
147 views

Trying to understand P vs NP vs NP Complete vs NP Hard

I am trying to understand these classifications and why they exist. Is my understanding right? If not, what? P is polynomial complexity, or O(nk) for some non-negative real number k, such as O(1), ...
-1
votes
1answer
60 views

Big O of loop of 0…n with nested loop doing k iterations [duplicate]

My coworkers and I are discussing this code and need a third party to settle our discussion :) Random randNum = new Random(); int[] A = Enumerable.Repeat(0, 1000).Select(i => randNum.Next(0, ...
0
votes
0answers
39 views

Bounded Priority queue with constant time amortized delete min and insert

Given a bounded priority queue (with keys between 1 and k), is there any data structure with amortized constant time for delete min and insert and find min, where the worst case time for these ...
2
votes
1answer
119 views

How to sort a list containing bounded set of values in linear time when length is unknown?

Given a list of integers whose length is unknown, and each of its elements lies between 1 to 1000, how does one sort this list in linear time?
3
votes
1answer
112 views

What is time complexity of update in binary heap?

For a binary heap we have O(log(n)) for insert, O(log(n)) for delete min and heap construction can be done in O(n). In the context of using a binary heap in Djikstra, my exam paper involved an ...
2
votes
1answer
141 views

Time Complexity when Loop Variable Depends upon Outer Loop Variable

What is the time complexity of the following piece of code in worst case? s = 0; for( i = 1; i <= n; ++i ) { for( j = 1; j <= i * i; j++ ) { for( k = 1; k <= j and j % i == 0; ...
1
vote
3answers
224 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
187 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 ...
1
vote
1answer
44 views

How an add vertex operation could be performed in constant time for a graph represented using adjacency list?

Adding a vertex in a graph that is represented using an adjacency list takes O(1) time complexity according to http://bigocheatsheet.com/ (graph operation > adjacency list > add vertex). It is said ...
3
votes
1answer
140 views

why adding a vertex in a graph represented using an adjacency matrix takes O(|v|^2) time complexity?

Adding a vertex in a graph that is represented using an adjacency matrix takes O(|v|^2) time complexity according to http://bigocheatsheet.com/ (graph operation > adjacency matrix > add vertex). But ...
5
votes
3answers
550 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 ...
4
votes
3answers
2k views

Why is mergesort O(log n)?

Mergesort is a divide and conquer algorithm and is O(log n) because the input is repeatedly halved. But shouldn't it be O(n) because even though the input is halved each loop, each input item needs to ...
-2
votes
2answers
391 views

Difference between O(N^2) and Θ(N^2) [duplicate]

What is the difference between O(N^2) and Θ(N^2)? I know that O is the upper bound and Θ is tight bound. Could someone explain me this concept with an example.
-1
votes
3answers
349 views

What is O(m+n) and O(m*n) in Big O notation? [duplicate]

I understand that O(n) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. An example of this is a for loop: for n in 0.100 puts ...
3
votes
1answer
77 views

Big-O for Immutable Trees

How would you calculate the time and space complexity for a tree algorithm that creates a copy of a tree, but reuses as much of the original tree as possible? For example, A /|\ B C G /|\ D ...
3
votes
1answer
146 views

What is the time complexity of this program?

An algorithm is given on GeeksForGeeks.com for constructing a Binary Search Tree from its preorder traversal. They say that the time complexity for the following code is O(n^2). But in my opinion it ...
1
vote
2answers
587 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
2
votes
1answer
79 views

Seeds distribution algorithm with complexity better than O(n^3)?

I have included my approach and solution. My solution works fine, however, is unoptimized with O(n^3) complexity An NGO is running seed distribution program. It has limited quantity of varied quality ...
1
vote
2answers
198 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 ...
-3
votes
4answers
177 views

Time complexity of this loop [duplicate]

Is the time complexity for this loop O(n) or O(log n)? for(i=0;i<n/2;i++){} I am thinking, the time is proportional with the input size.
7
votes
2answers
579 views

Big O equivalence for LINQ select

I'm trying to determine if there is a change in the Big O equivalence of a nested loop when I use a LINQ select instead. public void myFunc(List<Foo> fooList, List<Bar> barList) { ...
1
vote
1answer
188 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 ...
1
vote
1answer
1k 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 ...
10
votes
9answers
4k views

Big O Question about an algorithm with (n^2 + n) / 2 growth rate

I'm asking this question because I am confused about one aspect regarding big O notation. I am using the book, Data Structures and Abstractions with Java by Frank Carrano. In the chapter on the ...
-3
votes
1answer
133 views

Big O notation for a sub linear algorithm [duplicate]

I have a function for which the complexity raise by the square ten of the exponent of the number. Ex: +-----+----------+ |Input|Complexity| +-----+----------+ |0 | 1 | |10 | 2 | ...
1
vote
2answers
262 views

Big graph traversal with OOP

I'm trying to solve a algorithmic contest's problem. I have a matrix 2000x2000. I want to represent it as graph and traverse it with BFS/DFS. I have time limits on app running (2s). Simple vertices ...
0
votes
2answers
130 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) ...
2
votes
1answer
82 views

If I replace N objects with N pointers, is my space complexity still O(N)?

Lets say I get N objects as input, and I need to rearrange them into a different data structure. This means the space complexity of my algorithm will be O(N). But what if I replace the objects with ...
0
votes
2answers
770 views

How does big O notation indicate upper bound on a function? [duplicate]

Suppose we have a function, f(n)=n+10. We say that f(n)∈O(n), meaning O(n) represents the upper bound of the function. It is also true that f(n)∈O(n2) or f(n)∈O(n3) and so on. So how can we say that ...
0
votes
2answers
225 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 ...
21
votes
2answers
10k views

Algorithm to merge two sorted arrays with minimum number of comparisons

Given are two sorted arrays a, b of type T with size n and m. I am looking for an algorithm that merges the two arrays into a new array (of maximum size n+m). If you have a cheap comparison ...
0
votes
1answer
78 views

What would be the best sort to use on a something with sorted “chunks”?

Imagine a sorted deck of N cards that has been cut K times by moving X cards from the top to the bottom (X is a different / random amount each time, X is always < N) - what would be the best way to ...
0
votes
1answer
97 views

Handling the process of large-scale lists [closed]

What are the efficient ways to process huge lists (+10 millions), and things to consider while manipulating huge lists. First question, when should I use recursion, and when I shouldn't. In both ...
0
votes
1answer
402 views

Big O notation allocate array of N element

In Big O notation, allocate an array of N element is defined by O(1) or O(n) ? For example in C#, if I allocate an array like this : int[] a = new int[10] When I display this array, I have : ...
2
votes
1answer
560 views

Quickest sorting algorithm for sorting a low number of integers

I am making a program on my spare time that I want to run as quickly as possible. The program is written in C. A large set of the procedures operate on pointers to 7 integers that are sorted by their ...
4
votes
2answers
643 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 ...
17
votes
5answers
7k 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; ...
0
votes
1answer
145 views

Big O notation for the algorithm

What would be the big o for the algo: for (i=0; i < n*n; i++) for(j=0; j<i*i; j++) As per my understanding 1st loop will loop upto n2 times. 2nd loop will go around n2 times. Am I right or ...
3
votes
2answers
787 views

What does 'upper bound' mean in context of BigO?

My computer science teacher says Big O has an upper bound but no lower bound. When I look at a graph of an algorithm mapped out using BigO though, there isn't an upper bound at all. The upper limit ...
8
votes
2answers
1k views

single for-loop runtime explanation problem

I am analyzing some running times of different for-loops, and as I'm getting more knowledge, I'm curious to understand this problem which I have still yet to find out. I have this exercise called "How ...
2
votes
1answer
363 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; ...
0
votes
2answers
4k views

Running time of simple for-loops

I'm reading algorithms and I understand most of it, one thing that I can still struggle with a lot is something as simple as running times on different for-loops. Everyone seems to have easy with ...
0
votes
3answers
429 views

Why is the complexity of fetching a value from an array be O(1)?

How come the complexity of fetching a value from an array by it's index is O(1)? I thought the algorithm has to go through all the indexes, find the correct index, and then know what value to return. ...
0
votes
1answer
556 views

problem on calculating Big O complexity

i have this function on which i have to calculate the time complexity with the Big O notation: public void print(ArrayList<String> operations, ArrayList<LinkedHashSet<String>> ...
1
vote
2answers
1k 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 ...
1
vote
2answers
261 views

What is a O(n) algorithm to solve this puzzle?

We are going to hold a meeting where everybody will speak in clockwise direction around a table. There are n people with n spots. Each person has a position preference (e.g. some want to go first, ...