Stack Overflow
Stack Overflow

Questions tagged [asymptotic-complexity]

Asymptotic complexity is an approximation of the edge case performance of an algorithm used to determine best and worst case scenarios.

796 questions
433
votes
5 answers

Difference between Big-O and Little-O Notation

What is the difference between Big-O notation O(n) and Little-O notation o(n)?
Jeffrey Lott
  • 7,171
  • 6
  • 28
  • 28
151
votes
8 answers

Throwing cats out of windows

Imagine you're in a tall building with a cat. The cat can survive a fall out of a low story window, but will die if thrown from a high floor. How can you figure out the longest drop that the cat can survive, using the least number of…
AndrewF
  • 6,852
  • 7
  • 29
  • 27
63
votes
2 answers

Is it a good idea to store data as keys in HashMap with empty/null values?

I had originally written an ArrayList and stored unique values (usernames, i.e. Strings) in it. I later needed to use the ArrayList to search if a user existed in it. That's O(n) for the search. My tech lead wanted me to change that to a HashMap and…
dozer
  • 861
  • 1
  • 11
  • 22
53
votes
7 answers

Why is the Big-O complexity of this algorithm O(n^2)?

I know the big-O complexity of this algorithm is O(n^2), but I cannot understand why. int sum = 0; int i = 1; j = n * n; while (i++ < j--) sum++; Even though we set j = n * n at the beginning, we increment i and decrement j during each…
Omar N
  • 1,720
  • 2
  • 21
  • 33
40
votes
14 answers

How can I find a number which occurs an odd number of times in a SORTED array in O(n) time?

I have a question and I tried to think over it again and again... but got nothing so posting the question here. Maybe I could get some view-point of others, to try and make it work... The question is: we are given a SORTED array, which consists of a…
AGeek
  • 5,165
  • 16
  • 56
  • 72
34
votes
6 answers

Asymptotic complexity of .NET collection classes

Are there any resources about the asymptotic complexity (big-O and the rest) of methods of .NET collection classes (Dictionary, List etc...)? I know that the C5 library's documentation includes some information about it (example), but I'm…
Igor Brejc
  • 18,714
  • 13
  • 76
  • 95
30
votes
6 answers

Time Complexity of the Kruskal Algorithm?

I am calculating time complexity for kruskal algorithm like this (Please see the algorithm in the Image Attached) T(n) = O(1) + O(V) + O(E log E) + O(V log V) = O(E log E) + O(V log V) as |E| >= |V| - 1 T(n) = E log E + E log E = E log…
Sonali
  • 631
  • 3
  • 9
  • 11
28
votes
2 answers

What are sublinear algorithms?

I have been asked the following question by one of my fellow mates. Which of the following expressions is not sublinear? O(log log n) O(n) O(logn) O(root(n)) I have gone through https://en.wikipedia.org/wiki/Time_complexity#Sub-linear_time but…
station
  • 6,715
  • 14
  • 55
  • 89
22
votes
4 answers

Asymptotically optimal algorithm to compute if a line intersects a convex polygon

An O(n) algorithm to detect if a line intersects a convex polygon consists in checking if any edge of the polygon intersects the line, and look if the number of intersections is odd or even. Is there an asymptotically faster algorithm, e.g. an O(log…
infinity_x
  • 223
  • 1
  • 2
  • 4
20
votes
6 answers

asymptotic tight bound for quadratic functions

In CLRS (Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein), for a function f(n) = an2 + bn + c they said Suppose we take the constants c1 = a/4, c2 = 7a/4, and n0 = 2·max(|b|/a, √(|c|/a)). Then 0 ≤ c1n2 ≤ an2 + bn + c ≤ c2n2…
Happy Mittal
  • 3,667
  • 12
  • 44
  • 60
20
votes
6 answers

What does it mean when it is stipulated that extra allowed space is O(1)?

If the above condition in a programming question is given and I am solving it using recursion then am I violating the constraints? It could be because recursion also uses stack? Is it right?
Jainab Bano
  • 227
  • 1
  • 6
15
votes
3 answers

Big O of an algorithm that relies on convergence

I'm wondering if its possible to express the time complexity of an algorithm that relies on convergence using Big O notation. In most algorithmic analysis I've seen, we evaluate our function's rate of growth based on input size. In the case of an…
screeb
  • 625
  • 6
  • 20
15
votes
1 answer

Why is time complexity O(1) for pow(x,y) while it is O(n) for x**y?

Why is time complexity O(1) of pow(x,y) while it is O(n) for x ** y? Check comment from agf here
Kumar Tanmay
  • 153
  • 1
  • 1
  • 8
15
votes
3 answers

Does a useful Haskell HashMap/HashTable/Dictionary library exist?

I'm looking for a monad-free, constant access query O(1) associative array. Consider the hypothetical type: data HT k v = ??? I want to construct an immutable structure once: fromList :: Foldable t, Hashable k => t (k,v) -> HT k v I want to…
recursion.ninja
  • 5,377
  • 7
  • 46
  • 78
15
votes
3 answers

Difference between O(m+n) and O(mn)?

I was trying to find the complexities of an algorithm via different approaches. Mathematically I came across one O(m+n) and another O(mn) approach. However I am unable to grasp or say visualize this. It's not like I look at them and get the "Ahh!…
Dubby
  • 1,154
  • 3
  • 16
  • 31
1
2 3
…
53 54