Mashed Articles

When we need to select an algorithm for a particular purpose, we should pay attention to its runtime characteristics: how fast it is; how much memory it uses; whether there’s a worst case for the algorithm’s execution speed; and so on. All these answers are expressed with the big-Oh notation, which I’ll describe later.

A common abstract data structure that’s used all the time in programming is the dictionary or associative array, which is sometimes known as a map. I call it an abstract structure because it can be implemented in myriad different ways, but it always has a specific interface. We’ll use the dictionary to investigate the runtime efficiency of various algorithms that can be used to implement it.

OK, so it’s not this kind of dictionary. We’re referring to a digital one. An associative array.

But first, a definition: a dictionary is a structure that holds name-value pairs. A name-value pair is an object that has a name – that’s used both to describe its value and as a key to find it – and a value, which can be anything at all. The classic example is a real-world dictionary, where the name is a word and its value is the word’s definition. However, don’t limit yourself to assuming the name is always some kind of text string. In reality, names can be integer values, bit strings, 128-bit GUIDs, dates or anything at all. That said, it’s helpful to assume that they’re text strings for now.

The dictionary has various operations that define its external interface. There’s the ‘Create’ operation, which creates a new dictionary, and the ‘Destroy’ operation, which releases any resources the dictionary is using and destroys the structure. A dictionary can only be used after ‘Create’ has been called, and once ‘Destroy’ is executed, it no longer exists. Since these operations are only used once each per dictionary, they won’t have much effect on the overall runtime and so we won’t discuss them any further.

When given a name, ‘Find’ will search for the name-value pair that matches and return its value or an error if the name is not found. ‘Exists’ will do the same, except it will merely return true or false according to whether the name is present or not. Since they’re virtually identical, apart from what they return, we’ll ignore ‘Find’ from now on.

Finally we have ‘Insert’ and ‘Delete’, which do what you’d expect: add a new name-value pair to the dictionary (returning an error if the name already exists), and remove the name-value pair that matches a given name, respectively. In general, ‘Delete’ won’t return an error if the name is not found, and sometimes ‘Insert’ will merely replace the value if the name already exists.

Now that we have our abstract data structure, let’s investigate first how to implement it and second analyse the efficiency of our implementations. We’ll look at a total of four implementations.

Name-value pairs

The first implementation is the most obvious: use an array of name-value pairs. ‘Exists’ is the first operation to think about. In essence, to see whether the given name is present, you would check every pair in the dictionary sequentially and stop when you found it. If the given name isn’t present, you would compare the name of every name-value pair to the given name. The more pairs there are, the longer it would take, but you can be even more precise than that. Suppose there were N pairs in the dictionary and each comparison took the same (constant) length of time – say t. Then it would take tN time units to find out the given name wasn’t present. Another way of putting this is that the time taken for the nonexistence check is proportional to N. In computer science, without going into too much rigorous mathematics, we say the runtime efficiency is O(N), pronounced ‘big-Oh of N’, although you can read it as ‘is proportional to N’.

So if it took so many seconds to find out that a given name wasn’t in a dictionary of 1,000 pairs, it would take twice as long for a dictionary of 2,000 pairs, and 10 times as long for a dictionary of 10,000 pairs.

What if the given name was in the dictionary? What could we say then? Well, it could be that the matching pair was the first item checked. In that scenario, we say the best case efficiency for ‘Exists’ is O(1), which you read as ‘is constant’ (in other words, it doesn’t depend at all on the number of items in the dictionary). But, of course, for that to happen, you’d have to be extremely lucky. You could be completely unlucky and be looking for the final item. Here the worst case efficiency is O(N) – the time taken would be proportional to the number of items in the dictionary.

On average, though, if you searched for every name in the dictionary, the efficiency would be O(N/2). Now comes the fun bit with big-Oh notation: since it essentially means ‘is proportional to’, you can take the 1/2 (a constant) out of the parentheses into the implied proportionality constant and say that the efficiency is O(N). We say that searching through the dictionary-as-array is O(N): twice as many items, twice as long.

‘Insert’ is simple: we add the new name-value pair to the end of the array, a constant O(1) operation. Hold on there though – we first have to search the array to find out if the name is already present or not. ‘Insert’ then degenerates to O(N), just like ‘Exists’. We get no benefits at all from the constant, quick, add-it-to-the-end operation; we still have to search.

‘Delete’, as I’m sure you can see, is at least O(N) as well – we have to do the search. There’s something else about ‘Delete’ that we have to take into account: we have to physically remove the name-value pair from the array. The simplest way of doing this is to simply take the final pair in the array and put it in the slot vacated by the pair that was removed: a constant O(1) operation. So, overall, ‘Delete’ is O(N); the search time will swamp the move-an-item time.

Sorted pairs

Let’s move on to the second implementation. This one is again an array, except this time we maintain the pairs in sorted order. This has the assumed requirement that the names are sortable and that, given any two unequal names, we can say that the first is smaller or greater than the second.

We’ll start off by analysing ‘Exists’ again. The array is in sorted order, so we can use binary search to try and find the name-value pair that matches. With binary search, we look at the middle item in the array. If it’s the one we want, we stop. If the one we want is less than this middle item, we know that, if it’s present at all, it’ll be in the first half of the array. If the one we want is greater than the middle item, we know it will be in the second half. We repeat this process with the half array we selected. We’ll either find the item immediately again, or we’ll have reduced the number of items we have to search to a quarter of the array. Ditto the next step, except we reduce the space we have to search to an eighth of the original array. And so on.

Again, consider the doesn’t-exist case. Say we start out with an array with 1,023 items. After one step, we’ll have discarded one item and will have identified a subarray of 511 items for the next step. After this next step, we’ll have reduced the search space to 255 items, and so on. At the 10th step we’ll have a tiny array of just one item, which we can easily compare. So all in all, we’ll have made 10 comparisons to find out that the given name is not present. What’s so special about 10? Well, it’s the logarithm to base two of 1024 (that is, 2ˆ10 = 1024). Again, without being too rigorous mathematically, we say ‘Exists’ is O(logN) when the name isn’t present.

Think of O(logN) this way: if it takes a particular length of time to find out that a given name isn’t present in a sorted array of 1,000 items, it will only take twice as long for an array of 1,000,000 items. If you square the number of items, you double the time taken. This is an extremely significant result, showing the importance of binary search. What if the given name is present? We can make the same analysis as before: best case is O(1), worst case is going to be the same as not finding it: O(logN), and so we say that, overall, ‘Exists’ is O(logN).

What about ‘Insert’ and ‘Delete’? Again, we have to search for the name, so it would seem that they’re both O(logN). But this time, consider what we must do to add (or remove) the name-value pair. For ‘Insert’, we have to make a hole in the array to put the new pair in, shuffling all the items greater than it along by one. For ‘Delete’, we have to shuffle the remaining pairs to close up the hole vacated by the removed pair. If we’re lucky, in both cases, we don’t have to move any items (that is, best case is O(1)); if we’re unlucky we have to move all of the remaining pairs (that is, worst case is O(N)). On average, it’s O(N) for all the shuffling we need to do. Since O(N) is bigger than O(logN) – for very large values of N the (in)efficiency of the moving of the items will swamp the efficiency of the search – we ignore the smaller proportionality and just use the larger one. We say ‘Insert’ and ‘Delete’ are both O(N).

Hash table

Now for the next implementation: the hash table. Without going into full detail, we have an array as the basic data structure. Again, we analyse ‘Exists’ first. To find an item in a hash table, we hash the given name to produce an index into the array. The hash is produced by a randomising type function that takes the name, chops it up and combines the parts to produce an integer value. That integer value is then reduced to a possible array index value by use of the mod operator. The hash function is designed so that similar names produce very different hash values.

Best case is that ‘Exists’ is O(1). That is, we create the hash for the given name, convert it to an index, go to that element in the array, and the pair we need is there and matches. No matter how many items are in the array, that process is constant. (Actually, the hash function is usually O(k) where k is the length of the name, but we’re ignoring that for now.)

What about worst case? Well, in practice we’ll find that many names will hash to the same array index value. These are called collisions and we need to implement a collision resolution strategy to deal with them. The simplest is known as chaining, where we chain the name-value pairs as, say, a linked list at each array element. In this case, once we’ve calculated the index, we then do a sequential search through the chain at that index.

To ensure that the chain is never too long, hash tables grow themselves periodically when their load factor (the number of pairs present divided by the number of array elements) reaches a particular value. To do this, a new array is created, and all the pairs are rehashed and inserted into the new array. This ensures that chains never grow beyond a few items, say five or 10. Since this isn’t dependent on the total number of items, it’s still constant and we say ‘Exists’ in a hash table is O(1) on average.

‘Insert’ is a more difficult operation to analyse. On the face of it, it’s O(1) – both the ‘Search’ and ‘Add’ functions are constant time operations in general – but every now and then, a reorganisation will take place on an insertion operation. In general, hash tables are written such that they double in size when they grow. This is a O(N) operation, but we can amortise it over all previous insertion operations, so that, overall, ‘Insert’ remains O(1). Best case then is O(1), worst case is O(N), amortised case is O(1).

The same types of arguments can be made about ‘Delete’, although in general we tend not to shrink a hash table anywhere near as often as we make it bigger. ‘Delete’ is then O(1), meaning that the amortised use of a hash table over all its operations is O(1). There is, of course, still that warning that every now and then you will hit the O(N) worst case on an insertion.

Binary tree

The next data structure we can use is a balanced binary search tree, such as a red-black tree. This, like the sorted array version, makes the assumption that names can be sorted.

In a binary tree, the efficiency of search operations is O(d), where d is the maximum depth of the tree (the number of levels from the root of the tree to the furthest leaf). Since a perfectly balanced binary search tree is equivalent to binary search on a sorted array (every link you decide to follow will enable you to ignore a whole chunk of the tree), ‘Exists’ is on average O(logN). Best case is still O(1), but what about worst case? That depends on the algorithm used to balance the binary tree. Balancing is never perfect but, using red-black trees as an example, we can prove that they’re constructed such that the longest path is a maximum of twice the length of the shortest path. If you like, O(2logN). Since 2 is a constant, we can take it out, making red-black trees O(logN) in the worst case for ‘Exists’.

For ‘Insert’ and ‘Delete’, there’s a lot of mathematics that can prove that they’re both O(logN) as well. In essence, the search is O(logN), and the addition of the new node or removal of the old node is O(1) on average.

So, overall, a red-black tree is O(logN) in all its operations. Perhaps more importantly, it has guaranteed O(logN) time even in the worst case. This means that some people will prefer to use a red-black tree for their dictionary instead of a hash table because they don’t want to hit the possibility of O(N) insertion.

Figure 1: Graphing some common big-Oh expressions (O(N^2) is cut off so we can see the others).

From this discussion, you should now have a basic understanding of how to read and understand big-Oh expressions and how to evaluate algorithms and data structures based on them. Figure 1, above, illustrates the runtime for various common big-Oh expressions.

Radix trees

Radix trees offer a further data structure that can be used for a dictionary. A radix tree stores prefixes to keys rather than complete keys in its nodes, and each node can have many children. A key is then found as a complete path through the tree from root to leaf – at each step down the tree, you compare another small part of the name to the next node.

Figure 2, below, shows an example radix tree storing a small set of words. In searching for ‘hostess’, we follow the left link from the root, matching host, then follow the middle link matching the ‘e’ and finally matching the ‘ss’ in the right node.
Unlike the other data structures we’ve looked at, the efficiency of a radix tree doesn’t depend on the number of name-value pairs, but instead on the length of the keys. All operations are essentially O(k), where k is the maximum name length in the radix tree. This can be greater than the balanced binary tree’s O(logN), for example, but in practice we find that the comparisons needed in a binary tree are also significant, so the radix tree can be a viable alternative.

Figure 2: A small radix tree, using middle dot to indicate end of word.

Ternary trees

Back in issue 282, I cited ternary search trees as a strong candidate for the data structure behind a dictionary. Ternary trees, like radix trees, have a runtime efficiency that’s dictated by the length of the keys rather than their number, but are much easier to implement. Ternary search trees and radix trees also have a further benefit: using them means you can easily produce a sorted list of names in the dictionary, as well as produce a prefix list (a list of names with a particular prefix).

Profiling

All of the efficiency results quoted in this article are theoretical. They are all of the form ‘for large values of N the efficiency is proportional to some expression in N’, but make no mention of the size of the constant of proportionality. Therefore, when deciding on which data structure to use in your dictionary, you should profile actual code running on your actual data. It’s pointless worrying, for example, about the efficiency of millions of items in a dictionary when you’ll only have 100.

Go beyond updates, PC Plus reveals some of the weird projects that Twitter has given birth to.

Twitter isn’t just about telling the world what you had for lunch, any more than the phone is just a way of calling Mum. It’s a communications platform in its own right now, and you can do amazing things with those 140 characters – automatically generating content, serving up data on demand, sharing photos and much more. But what if you’re not feeling inspired? We’ve gathered together some projects people have put together through the medium of Twitter. Some are funny, some are useful and some are plain odd – but all are more interesting than a simple status update.

1. Read (or write) a book

“It was the best of times, it was the worst of times.” One of the best known lines in all of literature, and there’s still 89 characters left. Twitter novels are served up in bite-size portions, and you don’t need any special software to do one yourself – just a manuscript and the ability to copy and paste. Get an intriguing introduction to a book by signing up for nothing but first lines, or if you fancy getting involved with an original Twitter story, check out We Tell Stories.

Some people have found another slant on the idea of Twitter books by serialising existing diaries. You can sign up for daily time-shifted entries from the likes of farm girl from 1937 and watch their lives unfold in quasi real-time.

2. Track the weather

As the winter chill froze the country earlier this year, many people were tweeting messages like ‘BA1 8/10 #uksnow’. What was that? It was a collaborative weather map that harnessed Twitter’s power to keep track of the UK’s current snow conditions. With everyone knowing that 2/10 meant ‘a few flakes’ and anything over 7/10 translated as ‘blizzard’, the map built up piece by piece as more and more people tweeted, giving a real-
time picture of which areas in the UK were experiencing snow. It may not have been entirely accurate, but neither was the official weather forecast, and this at least had the advantage of being interactive.

3. Kick the habit

Any diet or attempt to break an addiction benefits from keeping notes on your progress, and Twitter offers an easy way of reinforcing good behaviour. Get into the habit of tweeting important information on what you’re doing, and sneaking that chocolate bar/cigarette/entire black forest gateau becomes a much more public affair. Having an electronic copy of your intake also makes it much easier to work out how well you’re doing, especially if you need to count calories. For dieting, there’s Tweet What You Eat and for smokers there’s Qwitter. Compulsive auto-
tweeters may want to avoid these services, though: the only real hope for such Twitter addicts is for someone to sneak in and cut their internet connection.

4. Expand your brain

Twrivia is a daily Twitter-based trivia quiz. Follow @twrivia to receive a trivia question every day; each one is preceded by a 15-minute warning. The first five people to answer the question correctly score more points. There aren’t any prizes – it’s all about climbing the leaderboard and the fun of challenging your brain with a good trivia question.

Daily brainteasers in 140 characters or fewer. You can hit Google, but you won’t get in first if you do…

5. Change the world

As anyone who’s seen a hashtag spreading out and reaching people all across the world knows, Twitter excels at generating memes. Why not try putting that to good use by creating a Twitter-based petition? With Act.ly, you can pass around a URL and let people register their support in seconds. It won’t have the weight of a full postal campaign, but it should still work as a way of politely registering opposition to something you’re concerned about.

6. Monitor your friends

The dubious story of a best man rigging a newlywed couple’s bed with a weight monitor and tweeting their bedtime activities complete with stats on duration and frenzy may have rung every BS alarm ever created, but there’s no reason it couldn’t be done. Read the story and its claimed ending. If you’re unconvinced, why not break out a soldering iron and build something similar?

7. Become a spy/gangster/assassin

OK, not literally. MI5, Don Corleone and the Hashshashin may be on Twitter, but we don’t have their usernames. Instead, we’re talking about social games. Spymaster was the first game to make it big, with 140 Mafia and SNODS – currently offline following later. These games add a fictional layer to your existing contacts, which isn’t always popular with the people following you.

8. Give your household appliances a voice

Plants that tweet at you when they’re thirsty? Doable. Toasters that report when the toast is done? Old news. While the idea may sound silly, these ideas are a great example of Twitter moving beyond messaging. If you fancy doing something like this, you can even set up your appliance’s account to send you text messages. This means you don’t need to be at your PC to see what requires your attention, so the whole system should fit right into your daily life and existing phone systems. Handy!

Botanicalls kits let you wire your plants up to Twitter, letting you know if they want a drink, or are bored of hearing your voice.

9. Warn your loved ones

When disaster strikes, Twitter is becoming a vital communications system – as we’ve seen during the earthquakes in Haiti and the shootings in Mumbai. It’s also been used to warn friends about arrests in other countries and to get help to the top of a mountain. Might it save your life someday?

10. Kick up a fuss

Twitter has the world’s attention right now, and word spreads fast. If you’re a celebrity, it’s the perfect unfiltered platform, as film director Kevin Smith demonstrated when he complained about Southwest Air kicking him off a flight because of his weight. But the great thing about Twitter is that it doesn’t just give famous faces a chance to air their grievances to a wide audience – we all have a shot too. London blogger Robert Loch’s complaints about one club caught the attention of the tabloids, and stationery company Paperchase found itself in trouble after one artist found their work being used without permission and posted about it on the site.

11. Get things done

As easy as it is to waste time on Twitter, it can be helpful too. Sign up to a service like Remember The Milk and if you’re glued to Twitter all day long, at least you’ll be given reminders to be productive. They come as direct messages, so you’ll also get them via email, on your phone or however else you’ve opted to receive them.

12. Wash your 
mouth out

Here at PC Plus, we never ****ing swear. **** no. But if you’re having trouble minding your ****ing manners, ****ing head over to Cursebird to see how ****ing rude you really are. If the report fills you with shame, you can start ***ing your **** ***** out immediately.

13. Stream everything

For many people, Twitter is replacing the blog. You can post links to anything you like, but many services are making that process automatic. Tie Twitter in to Flickr and you’ll tweet about your favourite photos; add YouTube to post automatically about videos; and link up Xbox Live to share your latest achievements. If a service doesn’t do it automatically, there’s probably a plug-in somewhere. You’ll want to make sure it’s switched off for anything you don’t want friends to see, though…

14. See the world

Want to know what’s going on around the world? Visit and watch as tweets from every corner of the Earth pop up onto your screen. This is largely pointless, true, but it’s a great way to kill some time and see what everyone’s talking about.

15. Wear your words

Every now and again you find a tweet so perfect, so beautiful, that letting it slip into the archives would just be a crime. Why not get it on a T-shirt? At Tweetshirt come into their own – they show you your social graph in an easily sortable form. For clearing out the rubbish from your lists, try StopTweet.

17. Track packages

When you’re waiting for something exciting to arrive, there’s little worse than constantly having to log into the courier service’s website for updates. With TrackThis you can fire and forget, getting the latest news pinged straight to you. We hope every service offers something similar in the near future.

18. Interact with fictional characters

Not everyone on the internet is who they say they are, but some admit it. Hunt around and you can find Twitter accounts for every fictional character from Darth Vader and Superman to True Blood’s Sookie Stackhouse and Barney Stinson from How I Met Your Mother. These accounts aren’t usually official, and they occasionally get clamped down on – as happened with ABC when it found viewers tweeting as the characters from Mad Men – and tend to be parodies rather than actually trying to ‘be’ the Joker online. Still, they can be fun – as fans of Peep Show will have experienced when the ‘characters’ live-tweeted the newest series.

Get more involved with your favourite characters’ daily lives by following them on Twitter.

19. Build a bot

Want to create life of your own? Twitter bots are easy to create thanks to Botomatic. Using a simple rule-based system, you can build up a list of how you want the bot to behave when it receives messages and gets new followers. Then just give it a name and a description and unleash it on the world! These aren’t the kind of bots that can actually conduct a conversation with a human being, but they’re great at passing information on request or automating systems capable of posting onto websites. To see some of the bots people have made for Twitter, visit the Twitter Fan Wiki’s Bots page.

20. Thank someone

In the real world, you often thank someone by saying ‘I’ll buy you a drink’. This is another reason why Twitter is better than reality – with Foamee you can keep track of how many you still owe, and if anyone owes you a drink, you can redeem it without sounding like a grabby so-
and-so. You can offer people either a beer or a coffee and then mark the drinks as redeemed when your taste buds are satiated or your conscience is clear. If you want to receive a soft drink, though, you’ll have to stick with the old fashioned way of grabbing a free beverage – hanging around at the pub, letting whoever owes you a drink get a round in and then somehow slipping away right before your turn.

Twitter has been the social-networking world’s flavour of the moment for quite some time, however it’s not without its issues.

Could anything be more dangerous to the modern celebrity than Twitter? The media has always been ready to pounce on famous personalities’ smallest mistakes, but Twitter lends its high-profile users a foghorn. If Jonathan Ross (@Wossy) wasn’t already in enough trouble for leaving lewd messages on Andrew Sachs’ answering machine, his antics on Twitter made him an even juicier tabloid target. “Utterly unwepentant” sniffed The Daily Mail after Ross wrote an update stating “Suspension is fun” on the micro-blogging service during the period that his shows were off-air. Another Mail headline branded the 49 year-old presenter “shameless” after he tweeted, “I am very polite in person. I’m just not great with answering machines.”

And Ross isn’t the only famous Twitter user to find themselves in hot water following a carelessly worded tweet. The BBC’s technology correspondent Rory Cellan-Jones (@ruskin147) was asked via Twitter why he chose to omit Wordscraper from a piece on Facebook’s word game applications. “’Cos i couldn’t be bothered!” came the reply. Cellan-Jones’s response was promptly republished on a blog along with the withering comment, “Years from now, when British journalism has finally breathed its last, this phrase will be engraved on its tombstone.”

However, Cellan-Jones seemed to be intrigued rather than embarrassed by the matter, using it as inspiration for a blog on the tricky business of working out what is and isn’t appropriate to say on social-networking sites. “My throwaway remark has been turned into the basis for an indictment of the whole of British journalism,” he commented. “[It’s] a useful reminder that Twitter – like so many other online forums – is a public place, and what you say there may be used in evidence against you.”

To tweet, to whom?

Most of the time, people don’t see danger coming. “Because it’s more immediate, people are perhaps thinking even less about what they do,” says Iain Connor, a partner at technology specialist law firm Pinsent Masons. Tweets might have a short shelf life, he argues, “but that’s not to say that sufficient damage can’t be done in a short period of time”.

One person who knows this better than most is basketball team owner Mark Cuban (@mcuban). Cuban owns the Dallas Mavericks and, after a game in March, he used Twitter to complain that an opposing player wasn’t whistled for a foul. “How do they not call a tech on JR Smith for coming off the bench to taunt our player on the ground?” he fumed. A few days later the NBA smacked him with a $25,000 fine. Still, the billionaire managed to see the funny side of his punishment, adding “Can’t say no one makes money from Twitter now,” as he paid up.

You may not be a celebrity, but the wrong words could find you out of a job, in hot water with friends or facing charges.

Mark Borkowski is a PR expert who has represented Michael Jackson, Eddie Izzard and Van Morrison. He says that Twitter is “dangerous for anybody”, but that it poses particular risks for stars. “You’re live all the time – no editing,” he says. “[What someone] thinks about in the nanosecond that they’re tweeting could become an enormous issue, and it’s global.” No stars seem to have been permanently damaged by mis-tweeting yet, but it’s possible, says Borkowski. “It depends what you say. If you make a racist or outrageous comment then it’s very difficult to come back from.”

Today’s headlines

Twitter isn’t all self-immolation on the part of celebrities, either. With the ability of tweets to spread like wildfire – first across Twitter itself and then across news websites worldwide – a hacked account spells disaster. “Britney has passed today,” said a tweet on Britney Spears’ account (@britneyspears) after it was hacked in June. Spears had more than two million followers at the time, meaning that the ‘news’ travelled fast. But this isn’t the first – or last – time that Spears’ account has been hacked. Mid-November saw her account spammed with updates telling the world that the singer had started worshipping Satan, and back in January followers were surprised to see this message from the star: “Hi y’all! Brit Brit here, just wanted to update you all on the size of my vagina. It’s about four feet wide with razor sharp teeth.” Perhaps Spears and her team need to take password security a little more seriously in future.

Twitter attempts to limit the potential damage done by celebrity impersonators by using Verified accounts. “That means we’ve been in contact with the person or entity the account is representing and verified that it is approved,” says the site. But what about the impersonators that Twitter knows exist, yet continue to post in the celebrity’s name?

Verified accounts were Twitter’s first push towards professional services. Commercial accounts are on the way.

“Twitter’s pretty poor at actually taking off fakes,” says Borkowski, but the amount of damage done by hackers is usually limited. Big social-networking sites are “incredibly reasonable” when it comes to removing objectionable content, according to lawyer Iain Connor. “They need to keep their credibility [and] they need to keep their trusted brand,” he says.

Verified accounts don’t mean safety for the celebrity, however: they simply confirm that it was probably the star who wrote the message. Without the usual filter of PR managers, talent agents or editors to prevent the publication of anything potentially damaging, such accounts are a dream for the media. Twitter is “a newswire direct from the celebrity” that newspapers turn into stories, confirms Borkowski.

Business as usual

But even if individual stars are at risk from Twitter, corporations should be safe, shouldn’t they? After all, “just about every organisation has a PR department now,” according to Managing Director of Racepoint PR, Blaise Hammond. Racepoint PR manages public relations for social media sites such as Digg, eHarmony and BlogHer.

The illusion that all companies tread carefully with new services such as Twitter was shattered in June, however, when furniture retailer Habitat (@habitatuk) attempted to cash in on the site. The store tweeted about deals it was offering, then attempted to give its tweets greater visibility by attaching unrelated hashtags (a hash symbol followed by a keyword that enables Twitter users to search for and follow a popular ‘trending topic’). “#Mousavi Join the database for free to win a £1,000 gift card” read one tweet, disastrously mixing the Iranian presidential candidate with a drive to sign people to its mailing list. “#iPhone Our totally desirable Spring collection now has 20% off!” read another.

Habitat acted swiftly to remove the offending tweets, but the damage was done. The story was picked up by mainstream news organisations such as Sky and the BBC, provoking outrage that the company was abusing the hashtag system and essentially spamming users. Habitat was quick to acknowledge its blunder and offered contrition. “We are treating this very seriously,” said the company. “We were shocked when we discovered what happened and are very sorry for the offence that was caused. This is totally against our communications strategy.”

Adding irrelevant hashtags to marketing tweets was “incredibly stupid”, according to Hammond. “It was very easy to find out, and they got found out straight away.” He says companies need to think carefully about how they tweet. “Thoughtlessness coupled with stupidity equals big impact,” he says. “Common sense is missing in so many cases.” Even when a company has a specific Twitter strategy, “more often than not it’s not as good as it could be because they just don’t think about it enough”.

Gun, foot, aim, fire

While Twitter clearly poses problems for high-profile Twitterers, it can be a threat to individuals as well. Few know this better than Connor Riley (@theconnor), a student at the University of California in Berkeley who was offered a summer internship last year by networking giant Cisco.

“Cisco just offered me a job! Now I have to weigh the utility of a fatty paycheck against the daily commute to San Jose and hating the work” she tweeted to her followers. But she soon regretted it. “Who is the hiring manager? I’m sure they would love to know that you will hate the work. We here at Cisco are versed in the web” tweeted Tim Levad, a services consultant at Cisco, in response. Before long, the story had hit MSNBC, The Los Angeles Times and hundreds of blogs worldwide. Riley now calls her misguided tweet “a stupid mistake”, and says that it was the result of treating Twitter like Facebook, where only your close friends are able to see what you say.

Mark Borkowski advises celebrities on how to manage their ‘brand’ through social media sites.

However, Iain Connor notes that “it’s perfectly legal” for companies to monitor what their employees are up to on social-networking sites. “As an employee you have a duty of good faith to your employer,” he says. “That duty of good faith extends not just to your nine to five.”

So what’s a Twitterer to do? “Don’t drink and tweet,” advises Borkowski. More importantly, don’t take it too seriously. Borkowski says social media refusniks are dying out. “Take it with a pinch of salt and it’s fun, it’s interesting, and you learn more,” he recommends. Just remember to think twice before you say anything that you wouldn’t want your mother – or your employer – to read.